본문으로 바로가기

깊이 우선 탐색(depth-first search, DFS)


① 깊이 우선 탐색이란?


그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법

▷ 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않습니다.

▷ 깊이 우선 탐색의 중요한 특성더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점입니다.

깊이 우선 탐색 구현할 경우 : 스택(Stack)의 성질 활용(방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현)

    ※ DFS : 스택(Stack), BFS : 큐(Queue) 를 사용합니다.

알고리즘 해결할 경우 : '재귀 호출'을 이용해 해결 (재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문에)

▷ 깊이 우선 탐색은 그래프 전체의 구조를 파악하기 위해 사용되므로, 그래프의 구조상 한 번에 모든 정점을 다 볼 수 없는 경우에도 모든 정점을 다 방문할 필요가 있습니다.


▷ 연결 요소(component)를 컴포넌트라고 읽습니다.

▷ 열결되어 있지 않은 정점은 DFS로 방문할 수 없습니다. 결국 같은 색의 정점들끼리 하나의 컴포넌트를 이룹니다.

DFS 한 번당 하나의 컴포넌트를 방문하므로, 이 때 방문을 시도하는 횟수는 컴포넌트의 갯수가 됩니다.


② 깊이 우선 탐색 시간복잡도?


정점의 집합 : V간선의 집합 : E 로 표현합니다.

 무방향 그래프(undirected graph) : 간선의 방향이 없어 양 방향으로 이동 가능,  방향그래프(directed graph) : 간선의 방향으로만 이동 


인접리스트 : O (|V| + |E|)

  1. dfs()는 한 정점마다 한 번씩 호출되므로, 정확히 |V|번 호출합니다.
  2. 모든 정점에 대해 dfs()를 수행 후, 모든 간선을 정확히 한 번(방향 그래프) 혹은 두 번(무향 그래프) 확인함을 알 수 있습니다.

인접행렬    : O (|V|²)

  1. dfs() 호출 횟수는 |V|번입니다.
  2. 인접 행렬을 사용할 때는 dfs() 내부에서 다른 모든 정점을 순회하며 두 정점 사이에 간선이 있는가를 확인해야 하기 때문에 한 번의 실행에 O (|V|)의 시간이 든다.

③ 깊이 우선 탐색으로 그래프 순회

1번 노드부터 시작하겠습니다.

현재 정점 : 1

순서 : 1

스택 : 1

1번 노드와 인접한 2번,3번 노드 중 더 작은 2번 노드를 선택합니다. 

현재 정점 : 2

순서 : 1 2

스택 : 1 2

2번 노드와 인접한 4번,5번 노드 중 더 작은 4번 노드를 선택합니다. 

현재 정점 : 4

순서 : 1 2 4

스택 : 1 2 4

4번 노드에서 더이상 들어갈 수 없으므로 2번 노드로 돌아갑니다.

현재 정점 : 2

순서 : 1 2 4

스택 : 1 2 


2번 노드에서 아직 들어가지 않은 5번 노드로 들어갑니다.

현재 정점 : 5

순서 : 1 2 4 5

스택 : 1 2 5

5번 노드에서 더이상 들어갈 수 없으므로 2번 노드로 돌아갑니다.

현재 정점 : 2

순서 : 1 2 4 5

스택 : 1 2 

2번 노드는 이미 접근을 했기 때문에 1번으로 돌아갑니다.

현재 정점 : 1

순서 : 1 2 4 5

스택 : 1 

1번 노드에서 아직 들어가지 않은 3번 노드로 들어갑니다.

현재 정점 : 3

순서 : 1 2 4 5 3

스택 : 1 3

3번 노드와 인접한 6번,7번 노드 중 더 작은 6번 노드를 선택합니다. 

현재 정점 : 3

순서 : 1 2 4 5 3 6

스택 : 1 3 6


3번 노드와 인접한 6번,7번 노드 중 더 작은 6번 노드를 선택합니다. 

현재 정점 : 7

순서 : 1 2 4 5 3 6 7

스택 : 1 3 6 7

모두 탐색하여 더 이상 갈 곳이 없으므로, 스택을 순서대로 비워줍니다.

현재 정점 : 6

순서 : 1 2 4 5 3 6 7

스택 : 1 3 6 

모두 탐색하여 더 이상 갈 곳이 없으므로,스택을 순서대로 비워줍니다.

현재 정점 : 3

순서 : 1 2 4 5 3 6 7

스택 : 1 3 

모두 탐색하여 더 이상 갈 곳이 없으므로,스택을 순서대로 비워줍니다.

현재 정점 : 1

순서 : 1 2 4 5 3 6 7

스택 : 1 

모두 탐색하여 더 이상 갈 곳이 없으므로,스택을 순서대로 비워줍니다.

현재 정점 : 

순서 : 1 2 4 5 3 6 7

스택 : 

탐색 종료


▶최종 방문 경로 : 1 2 4 5 3 6 7



④ DFS 관련 알고리즘 문제


 코드 보기를 누르시면 제가 해결한 코드를 보실 수 있습니다.


(백준 1260) DFS와 BFS (https://www.acmicpc.net/problem/1260)

[설명]

▷ DFS의 경우 인접리스트를 활용한 방법으로 해결했습니다.


(백준 11724) 연결 요소의 개수 (https://www.acmicpc.net/problem/11724)

[설명]

▷ 컴포넌트의 성질을 활용하여, 인접리스트를 사용한 방법으로 해결했습니다.


(백준 10451) 순열 사이클 (https://www.acmicpc.net/problem/10451)

[설명]

▷ 백준 11724문제와 비슷한 방식으로 해결하면 됩니다.


(백준 2667) 단지번호붙이기 (https://www.acmicpc.net/problem/2667)

[설명]

▷ 2차원 배열의 좌표 계산이 핵심입니다.


(백준 4963) 섬의 개수 (https://www.acmicpc.net/problem/4963)

[설명]

▷ 백준 2267번 단지붙이기 문제와 푸는 방식은 같다.

▷ 주의할 점은 처음에 제공하는 값이 w(너비), h(높이)이므로 2차원배열 생성할 때 new int[h][w]순으로 반대로 넣어주어야 한다.





참고

  1. 프로그래밍 대회에서 배우는 알고리즘 문제해결전략
  2. https://kks227.blog.me/220769870195



댓글을 달아 주세요