1. 방문(전파) 가능한 노드 갯수 구하기
한 정점에서 출발해 닿을 수 있는 정점이 몇 개인가를 묻는 유형이다.
탐색을 한 번 돌리면서 방문 표시를 세면 끝이라, DFS든 BFS든 상관없다. 거리를 묻지 않기 때문이다.
def count_reachable(graph, start):
visited = [False] * len(graph)
stack = [start]
visited[start] = True
count = 0
while stack:
node = stack.pop()
count += 1
for nxt in graph[node]:
if not visited[nxt]:
visited[nxt] = True # 넣을 때 표시한다
stack.append(nxt)
return count
방문 표시는 큐에 넣을 때 한다. 꺼낼 때 표시하면 같은 정점이 큐에 여러 번 들어가 시간이 늘고, 최악에는 간선 수만큼 중복된다.
출발점을 셀지 말지는 문제가 정한다. "출발점을 제외한 감염 노드 수" 같은 조건이면 -1을 해준다.
2. 목적지까지 최단거리
시작점에서 도착점까지 간선을 최소 몇 개 지나는가를 묻는 유형이다.
여기서는 반드시 BFS다. BFS는 가까운 곳부터 층층이 넓혀 가므로, 어떤 정점에 처음 닿은 순간이 곧 그 정점까지의 최단거리다. DFS는 깊이 먼저 파고들어서 먼저 닿은 길이 최단이라는 보장이 없다.
from collections import deque
def shortest(graph, start, goal):
dist = [-1] * len(graph)
dist[start] = 0
q = deque([start])
while q:
node = q.popleft()
if node == goal:
return dist[node]
for nxt in graph[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
q.append(nxt)
return -1 # 닿을 수 없다
방문 배열을 따로 두지 않고 dist의 -1 여부로 겸한다. 두 배열을 따로 두면 한쪽만 갱신하는 실수가 난다.
간선마다 비용이 다르면 이 방법이 통하지 않는다. 그때는 다익스트라를 쓴다 — 가중치 그래프 글 참고.
3. 독립된 지역의 갯수 구하기
서로 이어지지 않은 덩어리가 몇 개인가를 묻는 유형이다. 연결 요소(connected component)를 세는 문제다.
모든 정점을 훑으면서 아직 방문하지 않은 정점을 만날 때마다 탐색을 새로 시작하고, 그 횟수를 센다. 한 번의 탐색이 한 덩어리를 통째로 지우기 때문이다.
def count_components(graph):
visited = [False] * len(graph)
count = 0
for v in range(len(graph)):
if visited[v]:
continue
count += 1 # 새 덩어리를 만났다
stack = [v]
visited[v] = True
while stack:
node = stack.pop()
for nxt in graph[node]:
if not visited[nxt]:
visited[nxt] = True
stack.append(nxt)
return count
격자(2차원 배열)로 주어지는 문제도 같은 꼴이다. 섬의 개수, 단지 수, 그림 개수 같은 것들인데 이웃을 상하좌우 네 방향(또는 대각선까지 여덟 방향)으로 정의하는 것만 다르다.
바깥 반복문이 정점을 한 번씩 훑고 안쪽 탐색이 간선을 한 번씩 보므로 전체 O(V+E)다.
4. 정상 노드 감염시키기
한 정점에서 시작해 몇 번 만에 전체로 퍼지는가, 또는 시간 t에 몇 개가 감염되는가를 묻는 유형이다.
닿는 것만 세는 1번과 달리 몇 단계인지를 함께 따지므로 BFS를 쓴다. 층(level)을 세는 것이 곧 시간이다.
from collections import deque
def infect(graph, start):
dist = [-1] * len(graph)
dist[start] = 0
q = deque([start])
last = 0
while q:
node = q.popleft()
last = dist[node]
for nxt in graph[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
q.append(nxt)
return last # 전부 퍼지는 데 걸린 시간
출발점이 여럿이면 큐에 한꺼번에 넣고 시작한다. 하나씩 따로 BFS를 돌려 최솟값을 취하는 것보다 훨씬 빠르다 — 여러 곳에서 동시에 번지는 상황을 한 번의 탐색으로 처리한다(multi-source BFS).
q = deque(sources)
for s in sources:
dist[s] = 0
퍼지지 못한 정점이 남았는지는 마지막에 dist에 -1이 있는지로 본다.
5. 동일 위치에 재 방문이 가능한 경우
같은 정점을 다시 밟아도 되는 문제다. 이때 "정점 하나에 방문 표시 하나"로는 풀리지 않는다.
핵심은 무엇을 상태로 볼 것인가다. 위치만으로는 부족하고, 문제가 주는 조건을 함께 묶어야 한다.
- 벽을 k번까지 부술 수 있다 → 상태 =
(위치, 부순 횟수) - 낮과 밤에 규칙이 다르다 → 상태 =
(위치, 시간 % 2) - 열쇠를 모아야 문이 열린다 → 상태 =
(위치, 가진 열쇠 비트마스크)
방문 배열도 그 상태만큼 차원을 늘린다.
from collections import deque
# 벽을 최대 k번 부수며 (0,0) → (n-1,m-1) 최단거리
def bfs(grid, n, m, k):
visited = [[[False] * (k + 1) for _ in range(m)] for _ in range(n)]
q = deque([(0, 0, 0, 1)]) # y, x, 부순 횟수, 거리
visited[0][0][0] = True
while q:
y, x, broken, d = q.popleft()
if (y, x) == (n - 1, m - 1):
return d
for ny, nx in neighbors(y, x, n, m):
if grid[ny][nx] == 0 and not visited[ny][nx][broken]:
visited[ny][nx][broken] = True
q.append((ny, nx, broken, d + 1))
elif grid[ny][nx] == 1 and broken < k and not visited[ny][nx][broken + 1]:
visited[ny][nx][broken + 1] = True
q.append((ny, nx, broken + 1, d + 1))
return -1
같은 칸이라도 상태가 다르면 다른 자리다. 벽을 0번 부수고 도착한 칸과 2번 부수고 도착한 칸은 앞으로 갈 수 있는 길이 다르므로 따로 방문 표시를 둬야 한다. 이걸 합치면 더 나은 경로를 잃는다.
상태 수가 늘면 시간도 그만큼 는다. 위 예는 O(n \times m \times k)다.