이것이 취업을 위한 코딩 테스트다를 참고하여 작성하였습니다.

🖍️ 들어가기

• 그래프 : 노드(=정점, node)와 간선(=edge)로 이루어진 자료 구조
• 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것
• 두 노드가 간선으로 연결되어 있으면 두 노드는 인접하다 라고 표현한다.

그래프를 탐색하는 대표적인 두 가지 방법이 바로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 이다.

그래프를 표현하는 방법에는 두 가지가 있다.

• 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현
  • 연결되어 있지 않은 노드는 무한 비용으로 작성
  • 특정한 두 노드가 연결되어 있는지 정보를 얻어야 할 때 유리
• 인접 리스트: 리스트로 그래프의 연결 관계를 표현
  • 연결된 모든 관계에 대한 정보를 얻어야 할 때 유리

🖍️ DFS (깊이 우선 탐색)

DFS는 스택 자료 구조를 사용하며, 동작 과정은 아래와 같다

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 수행할 수 없을 때까지 방문한다.

# 재귀로 구현
def dfs_recursion(graph, v, visitied):
	# 현재 노드를 방문 처리
    visited[v] = True
    for i in graph[v]:
    	if not visited[i]:
	    	dfs(graph, i, visited)
            
# 스택으로 구현
def dfs_stack(graph, v, visited):
	stack = [v]
    visited = []
    
    while stack:
    	n = stack.pop()
        if not visited[n]:
        	visited[n] = True
        for m in graph[n]:
        	if not visited[n]:
            	stack.append(j)
            
graph = [
	[], # 인덱스 0은 비워둔다
    [2,3,8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]

visited = [False] * 9

dfs_recursion(graph, 1, visited)
dfs_recursion(graph, 1, visited)

🖍️ BFS (너비 우선 탐색)

DFS는 큐 자료 구조를 사용하며, 동작 과정은 아래와 같다

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 수행할 수 없을 때까지 방문한다.

from collections import deque
def bfs(graph, start, visited):
	queue = deque([start])
    
    # 현재 노드를 방문 처리
    visited[start] = True
    
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 원소를 하나 꺼냄
        queue.popleft()
   	for i in graph[v]:
    	if not visited[i]:
        	queue.append(i)
            visited[i] = True

graph = [
	[], # 인덱스 0은 비워둔다
    [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)

‼️ DFS는 인접 노드 넣고 → pop
‼️ BFS는 pop → 인접 노드 넣어