[Algorithm] DFS와 BFS

책 <이것이 코딩 테스트다 with 파이썬>을 바탕으로 작성한 글입니다.

0. 기본 개념

• 그래프: 노드(Node)와 간선(Edge)로 표현되며, 노드는 정점(Vertex)이라고도 함
• 그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것

두 노드가 간선으로 연결되어있을 때 '두 노드는 인접(adjacent)하다'고 표현함

• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프 연결 관계 표현하는 방식
  (연결이 되어 있지 않는 노드끼리는 매우 큰 수(ex. 99999999)로 작성)

• 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계 표현하는 방식

인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비되는 반면 인접 리스트 방식은 연결된 정보만 저장하기 때문에 메모리를 효율적으로 사용. 하지만 이 속성 때문에 인접 리스트 방식은 두 노드의 연결 여부에 대한 정보를 얻는 속도가 느림.

1. DFS

DFS(Depth-First Searh 깊이 우선 탐색)
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

DFS는 스택 구조를 이용함
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드 거냄
3. 2번의 과정을 계속해서 반복
(방문 처리: 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것)

1. 시작 노드 '1' 스택에 삽입하고 방문 처리
2. '1'에 대해 방문하지 않은 인접 노드 '2' 스택에 삽입, 방문 처리
3. '2'에 대해 방문하지 않은 인접 노드 '7' 스택에 삽입, 방문 처리
4. '7'에 대해 방문하지 않은 인접 노드 '6' 스택에 삽입, 방문 처리
5. '6'에 대해 방문하지 않은 인접 노드 없음, '6' 스택에서 꺼냄
6. '7'에 대해 방문하지 않은 인접 노드 '8' 스택에 삽입, 방문 처리
7. '8'에 대해 방문하지 않은 인접 노드 없음, '8' 스택에서 꺼냄
8. '7'에 대해 방문하지 않은 인접 노드 없음, '7' 스택에서 꺼냄
9. '2'에 대해 방문하지 않은 인접 노드 없음, '2' 스택에서 꺼냄
10. '1'에 대해 방문하지 않은 인접 노드 '3' 스택에 삽입, 방문 처리
11. '3'에 대해 방문하지 않은 인접 노드 '4' 스택에 삽입, 방문 처리
12. '4'에 대해 방문하지 않은 인접 노드 '5' 스택에 삽입, 방문 처리
13. 남아 있는 방문하지 않은 인접 노드 없음

결과 >> 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

def dfs(graph, v, visited):
	# 현재 노드 방문 처리
	visited[v] = True
    print(v, end='')
    
    # 현재 노드의 인접 노드 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드 방문 정보 리스트 자료형으로 표현 (초기화)
visited = [False] * 9

dfs(graph, 1, visited)

2. BFS

BFS(Breadth-First Searh 너비 우선 탐색)
가까운 노드부터 탐색하는 알고리즘

BFS는 큐 구조를 이용함
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 계속 반복

1. 시작 노드 '1' 큐에 삽입, 방문 처리
2. 큐에서 '1' 꺼내고 '1'에 대해 방문하지 않은 인접 노드 '2', '3', '8' 큐에 삽입, 방문 처리
3. 큐에서 '2' 꺼내고 '2'에 대해 방문하지 않은 인접 노드 '7' 큐에 삽입, 방문 처리
4. 큐에서 '3' 꺼내고 '3'에 대해 방문하지 않은 인접 노드 '4', '5' 큐에 삽입, 방문 처리
5. 큐에서 '8' 꺼내고 '8'에 대해 방문하지 않은 인접 노드 없으므로 패스
6. 큐에서 '7' 꺼내고 '7'에 대해 방문하지 않은 인접 노드 '6' 큐에 삽입, 방문 처리
7. 남아 있는 방문하지 않은 인접 노드 없음

결과 >> 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    # 현재 노드 방문 처리
    visited[start] = True
	
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 노드 하나 꺼내 출력
        v = queue.popleft()
        print(v, end='')
        
        #해당 노드와 연결된, 아직 방문하지 않은 노드 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)