깊이 우선 탐색 (DFS)

1. 개요

[그림 1] 깊이 우선 탐색 (Depth First Search)

 깊이 우선 탐색 알고리즘은 그래프 구조에서 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더 이상 갈 곳이 없게되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법이다. 

따라서, 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용 하거나 재귀호출을 통해서 구현한다.

---

2. 깊이 우선 탐색 예제 1 - 두 색으로 칠하기 (Binary Coloring) 

 평면위의 지도에서 서로 인접한 다른 영역을 구분하기 위해서 다른 색으로 칠하고자 한다. 어떤 연결 그래프가 주어졌을때 그 그래프를 두 색으로 칠할 수 있는지, 즉, 모든 정점을 빨간색 또는 파란색으로 칠할 때 인접한 정점이 같은 색으로 칠해지지 않게 할 수 있는지 알아보자. 문제를 간단하게 하기 위해서 몇가지 제한 사항을 둔다.

- 연결 그래프

- 무방향 그래프

- 자체 간선 (자신과 자신을 연결하는 간선)은 없다고 가정한다.

(Hint)

 주어진 그래프를 깊이 우선 탐색 (DFS)으로 순회하면서 이전에 방문했던 정점과는 다른 색으로 칠하면 된다. 만약 연결된 정점에 이미 색이 칠해져 있는데, 칠할 색과 다른 경우 두색칠하기가 불가능하게 된다.

void DFS_Matrix(int vNum, int col) { // 처음 시작점 RED 칠함 color[vNum] = col; // 0번부터 DFS 시작 (정점갯수만큼) for (int i = 0; i < vertexCnt; i++) { // 인접정점검사 ( 연결되어있으면 검사 ) if (graph[vNum][i] == 1) { if (color[i] == 0) DFS_Matrix(i, (col == RED) ? BLUE : RED); else if(color[i]==col) colorable = 0; } } }

파일입출력을 통해 그래프 인접정점 및 간선정보들을 입력받고 전역변수 colorable 를 통해 두색칠하기가 가능한지 불가능한지 판별하였다.

우선, 정점의 갯수만큼 color 배열을 만들고 0번 정점을 빨간색으로 설정하면서 DFS를 시작. 처음시작점을 지정한 색 RED로 넣고 정점갯수만큼 반복문을 돌려 인접정점이 있는지 먼저 검사하고 (연결되어있지 않으면 어느 색을 칠해도 상관없기 때문) 그 자리가 색이 칠해져있는지 검사하여 칠해져있으면 재귀호출을 통해 삼항연산자로 그 자리가 빨간색이었으면 파란색,, 파란색이었으면 빨간색을 칠하게 하도록한다.

그 자리가 이미 색이 칠해져있는 자리이고 현재 전달인자로 받은 color와 같다면 인접한 정점끼리 같은색이 칠해졌다는 것이므로 colorable변수를 0으로 바꿔주며 끝낸다.

---

2. 깊이 우선 탐색 예제 2 - 두더지 굴 프로그램

 재연이는 땅속의 굴이 모두 연결되어 있으면 이 굴은 한 마리의 두더지가 사는 집이라는 사실을 발견하였다.

재연이는 뒷산에 사는 두더지가 모두 몇 마리인지 궁금해서 특수 장비를 이용하여 뒷산의 두더지 굴을 모두 나타낸 지도를 만들어 내었다.

이 지도는 직사각형이고 가로 세로 영역을 0 또는 1로 표현한다. 0은 땅이고 1은 두더지 굴 영역을 나타낸다. 1이 상하좌우로 연결되어있으면 한 마리의 두더지가 사는 집으로 정의할 수 있다.

              

                                                                  [그림 1]                                        [그림 2]

[그림 2]는 [그림 1]을 두더지 굴로 번호를 붙인 것이다. 특수촬영 사진 데이터를 입력 받아 두더지 굴의 수를 출력하고, 각 두더지 굴의 크기를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

[입력]

첫번째 줄에 가로, 세로의 크기를 나타내는 n이 입력된다. (n은 30이하의 자연수)

두번째 줄에 n줄에 걸쳐서 n개의 0과 1이 공백으로 구분되어 입력된다.

[출력]

첫째 줄에 두더지 굴의 수를 출력한다. 둘째 줄부터 각 두더지 굴의 크기를 내림차순으로 한 줄에 하나씩 출력한다.

void dfs(int row, int col, int tNum) { tunnelInfo[tNum].number = tNum; // 현재 파는 터널의 번호 지정 if (inRange(row, col)) // 1) 검사할 좌표가 유효한지 검사 { if (map[row][col] == 1) // 1-1) 그곳이 1이라면 { map[row][col] = tNum; // 맵 내역을 현재 굴 번호 tNum으로 바꿔준다 ex) 1->2 tunnelInfo[tNum].size++; // 굴 사이즈 하나 증가 for (int i = 0; i < 4; i++) // 사방 재귀 dfs(row + RCXY[i].x, col + RCXY[i].y, tNum); } else // 1-2) 1이 아니면 return; } else // 2) 유효한 자리 아니면 돌아감 return; }

두더지굴의 정보를 그래프형식으로 받고 나타내어 DFS기법으로 문제를 해결하였다. 인접행렬을 이용해 나타난 그래프배열의 (0,0) 부터 순차탐색을 진행하여 (X,Y)의 값이 만약 1이라면 그 점을 시작으로 DFS를 시작, 모든 연결된 점을 해당 굴 번호로 체크한다. 모두 체크하면 다른 점으로 이동해 1이 있는곳을 또 확인하여 이전과정과 같이 반복하나 굴 번호를 1증가시켜 다음 굴번호로 저장한다.

[출력 예]