[WEEK03] 알고리즘_그래프, DFS, BFS

[WEEK03] 알고리즘_그래프, DFS, BFS

이번 주는 DFS(Depth First Search) 깊이 우선 탐색, BFS(Breadth First Search) 너비 우선 탐색에 대한 내용을 학습한다.

이 두가지 방법은 그래프의 탐색 기법으로 그래프에 대해 먼저 알아보자.

 

그래프

 

그래프는 정점(노드)과 간선(엣지)으로 이루어진 자료구조를 의미한다.

또한 간선의 방향의 유무에 따라 단방향 그래프, 무항향(양방향) 그래프로 나뉜다.

 

그래프를 표현하는 방식은 인접 리스트, 인접 행렬 두가지로 나뉜다.

일반적으로 인접 행렬이 많이 사용된다.

두가지 모두 익숙해져서 문제에 맞는 방법을 이용할 수 있도록 해야겠다.

 

1) 인접 행렬 그래프 - 모든 정보를 저장

- 장점 : 직관적, 쉽게 구현 가능

- 단점 : 모든 행렬 원소를 저장해야 하므로 불필요한 정보의 저장으로 인한 메모리 초과 발생 가능

- 구현 : 주로 int형의 2차원 배열, 연결 되어있으면 1, 없으면 0으로 표기

 

2) 인접 리스트 그래프  - 갈 수 있는 곳만 저장

- 장점 : 필요한 정보만 저장하여 메모리 절약 가능

- 단점 : 인접행렬에 비해 다소 어려움

- 구현 : 리스트나 벡터를 이용

 

 

 

DFS(Depth First Search)

 

루트에서 연결된 정점을 하나 선택하여 최대한 깊게 파고들어 그 자식들을 모두 탐색 방법이다.

재귀를 이용하는 경우가 많고 스택을 이용하여 구현할 수도 있다.

 

알고리즘 순서(백트래킹)

1.  깊이 파고들면서 더이상 갈 수 없을 때까지 내려감
2.  더이상 못 가면 한칸 올라가서 다른 자식 탐색, 탐색해야할 다른 자식이 없는 경우 한 칸 더 올라감
3.  2. 반복

 

장점

• BFS에 비해 저장공간이 덜 필요
• 찾아야하는 노드가 깊은 단계일수록 BFS보다 유리

 

단점

• 1. 답이 아닌 경로가 매우 깊다면 그 경로에 깊이 빠짐
• 2.  찾고있는 과정에서의 최단경로가 끝까지 탐색했을 때의 최단경로가 된다는 보장이 없음

 

 

 

DFS 알고리즘

 

무방향, 인접 리스트, 재귀 사용

import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

n,m,v = map(int, input().split())
visited = [False] * (n+1)
graph = [] # 리스트로 구현
for _ in range(n+1):
    graph.append([])
for i in range(m): # 무방향일때
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

dfs(1)

 

무방향, 인접 행렬, 재귀 사용

 

import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = 1
    print(v, end=' ')
    for i in range(n+1):
        if visited[i] == 0 and graph[v][i] == 1:
            dfs(i)

n, m, v = map(int, input().split())
visited = [0] *(n+1)
graph = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

dfs(1)

 

BFS(Breadth First Search)

 

너비 우선 탐색은 루트부터 시작하여 깊이별로 가로방향을 먼저 탐색하는 방법이다.

반복문에서 큐를 사용하여 FIFO(First in First out)의 순서로 pop하는 방식을 이용한다. 그 노드의 자식이 존재하면 queue에 append한다.

queue에 원소가 더이상 존재하지 않을 때까지 실행한다.

 

알고리즘 순서

1. 루트부터 시작하여 가까운 자식 노드들을 다 탐색 한다.
2. 그 자식 노드들과 연결된 아래 자식노드들을 다 탐색한다.

장점

• 너비를 우선으로 탐색하여 답이되는 경로가 여러 개인 경우에도 최단경로임을 보장
• 최단경로가 존재한다면, 어느 한 경로가 무한히 깊이 빠져도 최단경로를 반드시 찾을 수 있음
• 노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리

 

단점

• 재귀를 사용하는 DFS와 달리 큐를 이용해 다음 탐색 노드들을 저장. 노드의 수가 많을수록 필요없는 노드로 인해 더 큰 저장공간이 필요
• 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기 때문에 비현실적

 

 

 

BFS 알고리즘

 

무방향, 인접 리스트, 반복문 사용

 

from collections import deque
import sys
input = sys.stdin.readline

def bfs(start):
    queue = deque([start])
    visited[start] = True
    while queue: # 재귀 대신 while 반복문 사용
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n,m,v = map(int, input().split())
visited = [False] * (n+1)
graph = [] # 리스트로 구현
for _ in range(n+1):
    graph.append([])
for i in range(m): # 무방향일때
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i in range(1,n+1):
    graph[i].sort()

bfs(1)

 

무방향, 인접 행렬, 반복문 사용

 

from collections import deque
import sys
input = sys.stdin.readline

def bfs(start):
    queue = deque([start])
    visited[start] = 1
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in range(1, n+1):
            if graph[v][i] == 1 and visited[i] == 0:
                queue.append(i)
                visited[i] = 1

n, m, v = map(int, input().split())
visited = [0] *(n+1)
graph = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1
    
bfs(v)

 

참고 사이트:

https://m.blog.naver.com/occidere/220923695595