그래프 탐색 알고리즘

❓ 그래프 탐색 알고리즘이란

그래프에서 원하는 데이터를 찾는 알고리즘
코딩 테스트에서 매우 자주 등장한다

그래프는 2차원 배열, 인접행렬 등으로 표현할 수 있다.

대표적인 알고리즘: DFS, BFS

DFS(Depth-First Search)

: 깊이 우선 탐색
: 스택 자료구조 / 재귀 함수를 이용

탐색 순서

1 → 2 → 7 → 6 → 8 → 3 → 4 → 5 (숫자가 작은 경우 우선 탐색)

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 삽입하고 방문 처리
3. 방문하지 않은 인접 노드가 없으면, 최상단 노드를 꺼냄
4. 2번의 과정을 수행할 수 없을 때까지 반복

구현

def dfs(n, graph, visited):
  visited[n] = True  # 방문 처리
  print(n, end=' ')
  for adj in graph[n]: # 인접 노드
    if not visited[adj]: dfs(adj, graph, visited)

# 그래프를 표현하기 위해 2차원 리스트 사용
# 각 노드가 연결된 정보를 표현
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * len(graph)
dfs(1, graph, visited) # 1 2 7 6 8 3 4 5

---

BFS (Breadth-First Search)

: 너비 우선 탐색

• 큐 자료구조를 이용
• 최단 경로 문제 해결에 효과적

탐색 순서

1 → 2 → 3 → 8 → 7 → 4 → 5 → 6
: 1번 노드로부터 거리가 가까운 노드부터 방문

• 거리 1 : 2, 3, 8
• 거리 2 : 7, 4, 5
• 거리 3 : 6

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 꺼낸 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 큐에 삽입하고 방문 처리
3. 2번의 과정을 수행할 수 없을 때까지 반복

구현

from collections import deque

def bfs(start, graph, visited):
  queue = deque([start])
  visited[start] = True
  while queue:
    n = queue.popleft()
    print(n, end=' ')
    for adj in graph[n]: # 인접 노드
      if not visited[adj]:
        queue.append(adj)
        visited[adj] = True # 방문 처리

graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * len(graph)
bfs(1, graph, visited) # 1 2 3 8 7 4 5 6