C언어 알고리즘 - 깊이 우선 탐색(DFS)

깊이 우선 탐색 = DFS

트리의 순회와 같이 모든 정점들을 순서에 따라 방문하는 알고리즘을 탐색 알고리즘이라 합니다. 탐색 중에 가장 널리 쓰는 것이 깊이 / 너비 우선 탐색입니다. 일단 깊이 우선 탐색부터 하겠습니다.

DFS는 한 마디로 >현재 정점과 인접한 간선을 보고 안 간 곳을 따라가다 갈 곳이 없으면 돌아가는 탐색< 입니다.

동작 과정은 이러합니다.

이런 그래프가 있을 때 

a-b-f-h 로 들어가고 h에서 b로 가야 되는데 이미 방문한 노드라 무시되고 f로 돌아갑니다.

g-f-b-c-d-c-e까지 하고 e에서 a로 가야 되는데 역시 방문한 노드라 무시됩니다. 

c-b-a 순으로 돌아가면 탐색이 끝납니다.

코드는 재귀함수로 간단히 할 수 있습니다.

chk배열은 정점을 방문했는지 체크하는 배열

map배열이 그래프의 인접 리스트를 표현합니다.

 

모든 인접 정점을 순회하면서 아직 방문한 적 없다면 방문합니다.

더 이상 방문할 정점이 없으면 재귀 호출 종료, 이전 정점으로 돌아갑니다.

 

dfsall은 모든 정점을 방문합니다. 이 함수가 왜 필요하냐면

 

dfs의 성격 상 이렇게 생긴 그래프에서는 전체 탐색이 불가능 합니다.

그래서 모든 경우를 체크하려면 따로 함수를 만들어야 합니다.

DFS를 사용하는 문제입니다.

문제: https://www.acmicpc.net/problem/1260

코드: https://github.com/proqk/BOJ/blob/master/dfs/1260%20DFS%EC%99%80%20BFS.cpp

https://www.acmicpc.net/problem/11403

https://github.com/proqk/BOJ/blob/master/dfs/11403%20%EA%B2%BD%EB%A1%9C%20%EC%B0%BE%EA%B8%B0.cpp

https://www.acmicpc.net/problem/1012

https://github.com/proqk/BOJ/blob/master/dfs/1012%20%EC%9C%A0%EA%B8%B0%EB%86%8D%20%EB%B0%B0%EC%B6%94.cpp