그래프 이론 - 1. DFS (깊이 우선 탐색) / BFS (너비 우선 탐색)

DFS (Depth First Search, 깊이 우선 탐색) / BFS (Breadth First Search, 너비 우선 탐색) 

그림 출처: 나무위키

 

DFS, BFS는 그래프 문제에서 가장 기본적인 알고리즘들로, DFS와 BFS는 탐색을 진행할 때 우선시하는 방향에 따라 구분할 수 있다. 

 

 

DFS

원리

1. 먼저 시작하는 정점과 인접한 정점들을 방문 배열에 추가하고, 배열의 끝 부터 탐색을 시작한다.
   • A에서 시작한다고 가정하면 [B,C,D]를 배열에 추가하면 된다.
   • 배열의 끝에 있는 D를 배열에서 꺼낸다.
2. 인접한 정점을 아직 방문하지 않았다면, 해당 정점으로 이동한 후, 해당 정점과 인접한 정점들을 배열에 추가한다.
   • D와 인접한 정점은 [H] 이므로 H를 배열의 끝에 추가하면 된다.
3. 위의 과정을 더 탐색할 정점이 없을 때 까지 반복한다.

 

추가 설명

• 배열의 끝 부터 탐색하는 이유는, Python List는 끝에 원소를 추가하거나 제거하는 데 O(1)의 시간 복잡도를 가지는데 반해, 앞에 원소를 추가하거나 제거할 시 O(n)의 시간 복잡도를 가지기 때문.
• DFS의 원리 상 가장 마지막에 추가된 정점을 먼저 탐색하는데, 이와 같은 방식을 LIFO(Last In First Out, 후입선출)이라 부르고, 이 같은 특성을 갖는 자료구조를 스택(Stack) 이라고 부른다.
• 스택은 Python의 List를 통해 구현이 가능하다.
• DFS는 재귀함수로 작성이 가능하다. 반드시 재귀함수로 작성할 필요는 없지만, 문제 유형에 따라서 재귀함수로 작성할 시 풀이가 간편해지는 경우가 존재하기 때문에 작성하는 법은 알아두는 것이 좋다.

 

 

코드

# 입력값
# 정점의 갯수 n, 간선의 갯수 m이 주어짐
# m개의 간선이 (시작점 끝점)의 형태로 주어짐
# 정점의 이름은 1~n의 정수, 1번 정점부터 탐색을 시작

# n: 정점의 갯수, m: 간선의 갯수
n, m = map(int, input().split())

#graph: 그래프의 인접 리스트
graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

# visited: 각 정점의 방문 여부를 체크하는 배열
# 인접 리스트와 마찬가지로 DAT 방식, 해당 정점을 방문하지 않았을 시 0, 방문했을 시 1
visited = [0]*(n+1) 

def dfs(start):
    # 스택에 시작 정점을 추가
    stack = [start]
    
    # 시작 정점의 방문여부를 1로 변경
    visited[start]=1
    
    # 스택에 방분할 정점이 없을 때 까지 실행
    while stack:
    
    	# 스택의 가장 끝에 있는 정점을 꺼냄
        current = stack.pop()

        # 꺼낸 정점의 인접한 정점들에 대해 다음을 실행
        for neighbor in graph[current]:
        
            # 만약 인접한 정점을 방문하지 않았을 시, 방문여부 체크 후 해당 정점에서 DFS를 새로 시작
            if not visited[neighbor]:
                visited[neighbor] = 1
                dfs(neighbor)

 

 

BFS

원리

1. 먼저 시작하는 정점과 인접한 정점들을 방문 배열에 추가하고, 배열의 앞 부터 탐색을 시작한다.
   • A에서 시작한다고 가정하면 [B,C,D]를 배열에 추가하면 된다.
   • 배열의 가장 앞에 있는 B를 배열에서 꺼낸다.
2. 인접한 정점을 아직 방문하지 않았다면, 해당 정점으로 이동한 후, 해당 정점과 인접한 정점들을 배열에 추가한다.
   • D와 인접한 정점은 [E] 이므로 E를 배열의 끝에 추가하면 된다.
3. 위의 과정을 더 탐색할 정점이 없을 때 까지 반복한다.

 

추가 설명

• 먼저 추가한 정점을 먼저 방문해야 하므로, 정점을 추가하는 방향과 꺼내는 방향이 달라야 한다.
• BFS의 원리 상 가장 먼저 추가된 정점을 먼저 탐색하는데, 이와 같은 방식을 FIFO(First In First Out, 선입선출)이라 부르고, 이 같은 특성을 갖는 자료구조를 큐(Queue) 라고 부른다.
• 스택은 Python의 내장 라이브러리 collections의 deque를 통해 구현이 가능하다.
• 가중치가 없는 그래프에서 BFS를 통해 얻어진 경로는 반드시 최단경로이다.

 

코드

# 입력값
# 정점의 갯수 n, 간선의 갯수 m이 주어짐
# m개의 간선이 (시작점 끝점)의 형태로 주어짐
# 정점의 이름은 1~n의 정수, 1번 정점부터 탐색을 시작

from collections import deque

# n: 정점의 갯수, m: 간선의 갯수
n, m = map(int, input().split())

#graph: 그래프의 인접 리스트
graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

# visited: 각 정점의 방문 여부를 체크하는 배열
# 인접 리스트와 마찬가지로 DAT 방식, 해당 정점을 방문하지 않았을 시 0, 방문했을 시 1
visited = [0]*(n+1) 

def bfs(start):
    # 스택에 시작 정점을 추가
    queue = deque([start])
    
    # 시작 정점의 방문여부를 1로 변경
    visited[start]=1
    
    # 큐에 방분할 정점이 없을 때 까지 실행
    while queue:
    
    	# 큐의 가장 앞에 있는 정점을 꺼냄
        current = queue.popleft()

        # 꺼낸 정점의 인접한 정점들에 대해 다음을 실행
        for neighbor in graph[current]:
        
            # 만약 인접한 정점을 방문하지 않았을 시, 방문여부 체크 후 해당 정점에서 DFS를 새로 시작
            if not visited[neighbor]:
                visited[neighbor] = 1
                queue.append(neighbor)