by
Oct 16. 2020
Python DFS
백문 문제 풀이 (2644)
DFS에는 Depth-First Search의 약자이며 BFS와 달리 모두 조회할 필요 없이 정답만 구하면 될 경우 이용한다. 주로 코딩테스트 중급문제에서 자주 출제된다. DFS는 백트래킹 기법에서도 사용할 수 있으므로 알아두면 좋다. 백트래킹 기법은 앞서 설명했다.
DFS를 공부하기 위해 백준 2644번 문제를 풀어보자
https://www.acmicpc.net/problem/2644
위와 같이 촌수관계가 있을 때 3과 7의 촌수는 3촌관계이다.3에서 출발하여 자기와 연결된 노드를 조회한다. 단 여기선 BFS와 다르게 중간에 다른 노드를 살펴보지 말고 끝까지 조회해본다.
3 -> 1 -> 2 -> 7 방법으로 조회하면 된다.
만약 다음과 같은 촌수관계 일 때 3과 4의 촌수 관계를 구하려면 어떻게 해야할까
3 -> 1 -> 2 -> 7 ->6 -> 7 -> 8 -> 4 와 같은 순서로 구하면 된다.
일단 끝까지 가보는 방법이다. DFS는 stack을 이용하며 소스코드는 다음과 같다. 앞에서 공부한 BFS와 소스코드가 거의 유사하다. 차이점이라면 BFS에는 방문한 노드를 visit배열에 표현했는데 여기서는 시작점과의 촌수를 relation 배열에 표현했다는 것이다.
