인프런 커뮤니티 질문&답변

안녕하세요, 인프런 AI 인턴입니다.

DFS와 BFS는 탐색 순서의 차이로 인해 특정 문제에 대한 해결 방식이 달라질 수 있습니다. DFS(Depth-First Search, 깊이 우선 탐색)는 한 방향으로 깊게 탐색을 진행하며, 가중치 계산 문제에서 최단 경로를 찾는 데에는 비효율적일 수 있습니다. 이는 DFS가 모든 가능한 경로를 탐색한 후에야 최단 경로를 찾을 수 있기 때문입니다.

반면, BFS(Breadth-First Search, 너비 우선 탐색)는 시작 지점으로부터 가까운 노드부터 넓게 탐색해나갑니다. BFS는 같은 거리를 가진 노드들을 동시에 탐색하므로, 가중치가 동일할 때 최단 경로 문제에 효과적입니다. 이는 BFS가 최단 경로를 보장하는 성질을 가지고 있기 때문입니다.

DFS를 사용하여 가중치를 계산할 수 있다고 하더라도, 특정 조건에서 최단 경로를 보장하지 못하는 경우가 발생할 수 있습니다. 예를 들어, 미로 탐색 문제에서는 모든 경로를 탐색해 보지 않고는 최단 경로를 알 수 없는데, DFS는 깊은 단계의 노드를 먼저 방문하기 때문에 불필요하게 긴 경로를 탐색할 수 있습니다.

질문하신 백준 2178번 미로 탐색 문제의 경우, 큐(queue)를 사용한 BFS로 가중치를 계산하는 것이 스택(stack)을 이용한 DFS보다 최단 경로를 효과적으로 찾을 수 있습니다. BFS는 같은 레벨의 모든 노드를 동일한 순간에 탐색하기 때문에, 미로 내에서 최단 거리를 보장하는 최적의 방법입니다. 따라서, DFS보다 BFS를 사용해야 하는 이유는 이러한 최단 경로를 효과적으로 찾기 위함입니다.

님이 직접 변형하여 시도해 보신 것처럼, 큐를 스택으로 바꾸면 BFS의 탐색 방식이 DFS로 변환되며, 이로 인해 탐색 순서가 달라져 최단 경로를 찾는 데 있어서 결과적으로 비효율적이거나 오답으로 이어질 수 있습니다.

위 설명이 궁금증을 해결하는 데 도움이 되었기를 바랍니다. 더 궁금한 점이 있으면 언제든 질문해 주세요!

안녕하세요 유태님 ㅎㅎ

가중치가 같을 경우, 가중치를 구하는 문제는 DFS가 아닌 BFS를 써야한다고 배워서 그런가보구나

>> 아닙니다. 가중치가 같은 그래프내에서 -> 최단거리로 쓰일 수 있는 것이 BFS입니다.

하지만 이러한 차이점이 있다고 하더라도, 좌표 값의 앞부터 사용하는 것이 뒤에서부터 사용하는걸로 바뀔 뿐인데 왜 오답처리가 되는지 이해가 되지 않아서 질문드립니다.

>> 스택을 사용하면 그건 BFS가 아닙니다. BFS는 시작 지점으로부터 가까운 노드부터 넓게 탐색해나가는 순서가 중요한데 stack은 그 순서를 지키지 못합니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.