DFS

投稿した質問数 32

0

안녕하세요 공부좀하자님.

먼저, 아파트 단지 번호 문제는 BFS, DFS 모두 사용 가능한 문제가 맞습니다.
그래프 탐색 알고리즘의 한 예시로서 기본적이고 직관적인 문제를 찾다보니 두 가지 알고리즘을 모두 사용할 수 있는 문제가 선별된 것으로 생각됩니다. 다만, 문제의 난이도가 높아지면 보통 둘 중에 한 개 알고리즘으로만 풀 수 있는 경우가 많습니다.

두 번째로, BFS는 최단경로 탐색을 보장하기 때문에 unweighted graph (엣지의 거리를 모두 1로 간주하는 가중치가 없는 그래프)에서 최단거리를 탐색할 때 용이합니다. 질문자님께서 생각하고 계신 부분이 맞습니다.
DFS의 활용과 관련된 답변을 드리자면, 이론적으로 BFS와 DFS는 상호대체 가능합니다. 그럼에도 메모리 부족 문제로 문제의 난이도가 높아지면 상호대체가 불가능한 경우가 많습니다. 이 경우 재귀적인 특성을 활용하여 메모리 부족 문제를 해결하며, 이를 위해 DFS를 사용한다고 생각해주시면 되겠습니다.
DFS를 사용할 수밖에 없는 한 예시로 스도쿠 문제를 예로 들 수 있습니다. 9x9 스도쿠에 45개의 빈칸이 있는 경우, 각 레벨당 9^n개의 노드를 가지는 의사결정트리가 만들어지며 최대 9^45개의 노드를 검사해야 합니다 (이는 대략적으로 추산한 값입니다. 실제로는 더 적거나 많을 수 있습니다). 이러한 트리를 BFS로 모두 검사하게 되면 제한시간 안에 풀지 못하는 것이 일반적이기 때문에, DFS를 활용하여 루트 노드에서 가장 낮은 레벨의 노드로 도달하는 방법을 찾아야 합니다.
문제링크: https://www.acmicpc.net/problem/2239

공부좀하자님이 만족하시는 답변이 되었기를 바라며, 답변 해결로 상태 변경을 부탁드립니다.

이후에도 문제를 풀거나 공부하시면서 어려운 점이 있다면 질문 올려주세요.

감사합니다.