모든 이동 비용이 같은 그래프에서 가장 적은 이동 횟수를 찾으려 합니다. BFS와 DFS 중 무엇이 맞나요?

모든 간선의 이동 비용이 같고 최소 이동 횟수를 찾는 문제라면 BFS를 사용하겠습니다. BFS는 출발점에서 거리 0, 1, 2인 정점을 층별로 처리하므로 어떤 정점을 처음 발견한 순간의 거리가 최소입니다. DFS는 한 경로를 깊게 따라가므로 목적지에 먼저 도착해도 더 짧은 경로라는 보장이 없습니다.

가중치와 메모리 조건을 나눕니다

시작점을 큐에 넣고 거리를 0으로 둡니다. 큐에서 하나를 꺼내 이웃을 아직 방문하지 않았다면 거리 +1로 표시하고 부모를 기록해 뒤에 넣습니다. 짧은 거리의 층을 먼저 처리하므로 처음 발견한 거리보다 짧은 경로가 뒤늦게 나타나지 않습니다. 목적지에서 부모를 거꾸로 따라가면 경로를 복원할 수 있습니다. 이 층별 처리를 너비 우선 탐색(Breadth-First Search)이라고 부릅니다.

방문 표시를 큐에 넣을 때 하지 않고 꺼낼 때 하면 같은 정점이 여러 번 들어가 메모리와 시간이 불필요하게 늘 수 있습니다. 목적지에 도달할 수 없으면 큐가 비워질 때까지 목적지를 찾지 못한 상태로 처리합니다. 여러 최단 경로가 있으면 부모 선택 순서에 따라 하나가 정해질 뿐, 모든 최단 경로를 반환한다는 뜻은 아닙니다.

DFS와 가중치 조건을 구별합니다

DFS는 스택 또는 재귀 호출로 한 방향을 깊게 탐색하므로 연결성 확인, 모든 경로를 열거하는 백트래킹, 위상 관계 같은 문제에 적합합니다. 재귀 DFS는 긴 사슬에서 호출 스택이 넘칠 수 있어 명시적 스택으로 바꿀 수 있습니다. 간선 비용이 다르면 이동 횟수가 적은 길이 총비용이 최소라는 뜻이 아니므로 BFS는 맞지 않습니다. 0과 1 비용만 있으면 0-1 BFS, 일반적인 음이 아닌 가중치는 Dijkstra, 휴리스틱으로 목적지 방향을 줄이면 A*를 검토합니다.

검증은 순환 그래프, 여러 최단 경로, 고립·도달 불가 정점, 긴 사슬, 동일 정점의 여러 진입을 포함합니다. 저장 표현이 인접 리스트인지 행렬인지와 무관하게 방문 거리·부모·큐의 불변식을 확인하고, 비용 모델이 바뀌면 알고리즘도 바꿔야 합니다. 핵심은 알고리즘 이름보다 최소화할 값이 간선 수인지 총비용인지 먼저 선언하는 것입니다.

BFS는 거리 0인 층을 모두 처리한 뒤 거리 1, 2 층으로 넘어가므로 동일한 간선 비용에서 처음 발견한 거리가 최소입니다. 큐에 들어가는 거리 순서가 감소하지 않는다는 것이 핵심 불변식입니다. 여러 시작점을 모두 거리 0으로 넣는 다중 시작 BFS와 부모 기록으로 최단 경로 하나를 복원할 수 있습니다.

양방향 BFS는 방향 그래프에서도 역방향 간선을 별도 표현해 반대쪽에서 탐색할 수 있으면 사용할 수 있습니다. 양쪽 탐색이 만났다고 즉시 종료하지 말고 현재 층 거리의 합과 다른 후보의 하한을 비교해야 합니다. 가중치가 0·1이면 0-1 BFS, 일반 비음수 가중치면 Dijkstra를 쓰며, 격자의 대각선·모서리 통과 규칙도 간선 정의에 포함해 검증하겠습니다.

최단 경로 개수까지 필요하면 처음 발견한 이웃의 거리를 설정하고 경우의 수를 넘긴 뒤, 같은 최단 거리로 다시 도착할 때 경우의 수를 더할 수 있습니다. 더 먼 경로는 합산하지 않습니다. 부모 하나는 경로 하나만 복원하지만 모든 부모를 저장하면 출력할 경로 수 자체가 지수적으로 커질 수 있으므로 거리 계산 비용과 출력 비용을 구분하겠습니다.