퍼져나가며 찾자! BFS와 DFS

• 격자와 그래프가 같은 것임을 안다.
• BFS를 큐로, DFS를 스택이나 재귀로 쓴다.
• 방문 표시를 언제 해야 하는지 안다.
• 최단 거리는 BFS만 준다는 것을 안다.

비유로 이해하기 — 지하철 노선도

역이 점이고 선로가 연결이라냥. "여기서 저기까지 몇 정거장이냥?"이 오늘 푸는 문제라냥.

격자에서는 칸이 점이고, 상하좌우로 붙어 있는 것이 연결이라냥. 그래서 8장의 방향표가 그대로 쓰인다냥.

격자가 아닌 그래프는 인접 리스트로 담는다냥. adj[u] 에 u 와 이어진 점들을 넣어두는 거라냥.

adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)      # 방향이 없으면 양쪽 다 넣는다냥

격자든 인접 리스트든 "지금 칸에서 갈 수 있는 곳들" 을 주는 건 똑같다냥. 그래서 알고리즘은 하나도 안 바뀐다냥.

방문 표시는 큐에 넣을 때 한다냥. 꺼낼 때 하면 안 된다냥.

꺼낼 때 표시하면, 아직 큐 안에서 기다리는 칸을 다른 이웃이 또 넣는다냥. 같은 칸이 큐에 여러 번 쌓인다냥.

작은 입력에서는 답이 맞게 나오기도 한다냥. 하지만 큐가 쓸데없이 부풀어서 입력이 커지면 느려지고 메모리도 먹는다냥. 처음부터 넣을 때 표시하는 습관을 들이자냥.

9장에서 배운 대로 큐는 deque 로 만들자냥. list.pop(0) 을 쓰면 칸 수가 많아질 때 그것만으로 느려진다냥.

dist 를 -1 로 채워두면 방문 표시와 거리를 한 배열로 해결한다냥. -1 이면 아직 안 간 곳이라냥. seen 을 따로 둘 필요가 없다냥.

끝나고도 -1 인 칸은 아예 갈 수 없는 곳이라냥.

최단 거리는 BFS만 준다냥. DFS로 먼저 도착한 경로는 최단이 아니라냥.

DFS는 한 방향으로 끝까지 파고들기 때문에, 빙 돌아가는 길로 먼저 닿을 수 있다냥. 오늘 3번 문제의 숨겨진 테스트가 정확히 그걸 잡는다냥.

가까운 곳부터 보는 BFS는 처음 닿았을 때가 곧 최단이라 그런 일이 없다냥.

재귀 DFS에는 깊이 함정이 있다냥. 7장에서 배운 그거라냥.

파이썬은 재귀가 1000번쯤 쌓이면 RecursionError 로 터진다냥. 그런데 격자가 크면 깊이가 쉽게 그걸 넘긴다냥.

import sys
sys.setrecursionlimit(10 ** 6)

이 한 줄로 풀린다냥. 오늘 2번 문제에 100 x 100이 전부 땅인 격자가 들어 있는데, 이 줄이 없으면 정답 코드도 터진다냥.

깊이는 칸 수가 아니라 파고든 길이라냥. 그래서 헷갈린다냥.

땅이 3000칸이어도 여기저기 흩어진 모양이면 깊이는 얕게 끝난다냥. 반대로 빈틈없이 꽉 찬 격자는 뱀처럼 훑고 지나가서 깊이가 칸 수만큼 된다냥.

큰 격자에서 깊이가 걱정되면 그냥 BFS를 쓰자냥. BFS는 큐를 쓰니 깊이 문제가 아예 없다냥.