알고리즘 4-1강. 깊이 우선 탐색(Depth First Search)

[탐색 알고리즘 강좌]

해를 찾기위해 전진, 또 전진!

깊이 우선 탐색(DFS, Depth First Search)

---

이번에는 깊이 우선 탐색(DFS, Depth First Search)이라는 알고리즘에 대해 알아보려고 합니다. 일반적으로 이 DFS 알고리즘을 구현할때는 스택을 이용하고, 트리 혹은 그래프 같은 자료구조에서 데이터를 탐색할 때 사용하는 알고리즘 입니다. 너비 우선 탐색이라고 해서 깊이 우선 탐색과 비슷한게 있는데, 너비 우선 탐색은 다음 강좌에서 소개할 예정입니다. 이 DFS 알고리즘은 더이상 나아갈 길이 보이지 않을 만큼 깊이 들어가는 특징을 지니고 있는데, 만약 나아갈 길이 존재하지 않으면 이전의 위치로 돌아와 다른 길을 선택하여 움직입니다. 이해하기 쉽도록 그래프를 보면서 설명을 하도록 하겠습니다.

깊이 우선 탐색(Depth First Search)의 방문 순서

그래프에선 어떻게 이동할까요? 자, 우선 그래프를 보도록 합시다.

여기서 원으로 둘러싸인 1, 2, 3, 4, 5.. 등을 정점(Vertex)이라 하고, 정점과 정점을 잇는 선을 간선(Edge)라고 하겠습니다. DFS 알고리즘은 인정사정 가릴것 없이, 방문했던 길이 아니라면 아무곳이나 이동합니다. 우선은, 1부터 시작하여 2부터 쭉 방문해 나가도록 하겠습니다.

위의 방문 순서를 보시면 '1 -> 2 -> 4 -> 8 -> 5 -> 6 -> 3 -> 7'과 같은 순서로 방문되고 있음을 보실 수 있는데, 모든 과정을 한번 살펴보도록 하겠습니다.

(1) 현재 위치는 정점 1이고, 정점 2, 3을 방문하지 않았으므로 우선은 정점 2로 이동한다.

(2) 현재 위치는 정점 2이고, 정점 1을 방문했으며, 정점 4, 5를 방문하지 않았으므로 우선은 정점 4로 이동한다.

(3) 현재 위치는 정점 4이고, 정점 2를 방문했으며, 정점 8을 방문하지 않았으므로 정점 8로 이동한다.

(4) 현재 위치는 정점 8이고, 정점 4를 방문했으며, 정점 5, 6, 7을 방문하지 않았으므로 우선은 정점 5로 이동한다.

정점 5로 이동한 후에 정점 2와 정점 8은 이미 방문된 곳이므로 더이상 갈곳이 없으니 전에 방문한 정점으로 돌아간다.

(5) 현재 위치는 정점 8이고, 정점 4, 5를 방문했으며, 정점 6, 7을 방문하지 않았으므로 우선은 정점 6로 이동한다.

(6) 현재 위치는 정점 6이고, 정점 8을 방문했으며, 정점 3을 방문하지 않았으므로 정점 3으로 이동한다.

(7) 현재 위치는 정점 3이고, 정점 1, 6을 방문했으며, 정점 7을 방문하지 않았으므로 정점 7로 이동한다.

(8) 현재 위치는 정점 7이고, 정점 3을 방문했으며, 정점 8번 노드는 이미 방문된 곳이므로 더이상 진행하지 않는다.

 

위 과정을 거친 후에야 이렇게 탐색은 종료되는 것이죠. DFS가 어떻게 움직이는지 감이 잡히시나요? 이번에는 위의 DFS 알고리즘을 코드로 구현하여 보도록 하겠습니다. 코드를 구현하기 전, 정점과 정점 사이의 인접 관계를 나타내기 위해서 인접 행렬(Adjacency Matrix)를 사용하도록 하겠습니다. 우선은 인접 행렬에 대해 간단히 살펴보도록 합시다. 여기서 인접 행렬을 아시고 계시는 분들은 건너뛰셔도 됩니다. (고등학교 수학 과정에서 행렬과 그래프 배우신 분들이면 다 아실거라 생각합니다.)

인접 행렬(Adjacency Matrix)

인접 행렬(Adjacency Matrix)이란 정점의 인접 관계를 행렬을 통해 나타내는 것을 말합니다. 인접 관계를 어떻게 행렬로 표현하는지, 간단한 그래프와 인접 관계를 나타내는 행렬을 아래에다 표시해두도록 했습니다.

만약 정점 i와 정점 j가 서로 연결되어 있는 관계일 경우에는 (i, j)가 1이며, 연결되지 않았을 경우에는 (i, j)에 0이 들어갑니다. 위 그림에서 그래프 옆에 있는 행렬이 인접 행렬이라는 것인데, 대각선을 기준으로 대칭이 됨을 보실 수 있습니다. 만약 정점 1과 정점 3이 연결되어 있는 상태일 경우에는 (1, 3)과 (3, 1)이 1임을 확인할 수 있습니다.

깊이 우선 탐색(Depth First Search)의 구현

자, 이제는 깊이 우선 탐색을 구현해보도록 합시다. 우선은 정점의 갯수를 N개로 제한하면, 인접 행렬의 크기는 N*N이 됩니다. 마찬가지로 정점의 갯수를 30개로 제한하면, 인접 행렬의 크기는 30*30로 2차원 배열로 만드시면 됩니다. 그리고 정점이 방문되었는지, 방문되지 않았는지를 알아내기 위해 크기 30의 배열을 놓도록 하겠습니다. 그럼 구현해보도록 할까요?

#include <stdio.h>

int n; // 정점의 총 갯수
int map[30][30], visit[30]; // 인접 행렬과 방문 여부를 나타내는 배열

void DFS(int v)
{
	int i;

	visit[v] = 1; // 정점 v를 방문했다고 표시
	for (i = 1; i <= n; i++) 
	{
		// 정점 v와 정점 i가 연결되었고, 정점 i를 방문하지 않았다면
		if (map[v][i] == 1 && !visit[i])
		{
			printf("%d에서 %d로 이동\n", v, i);
			// 정점 i에서 다시 DFS를 시작한다
			DFS(i);
		}
	}
}

int main()
{
	int start; // 시작 정점
	int v1, v2;

	scanf("%d%d", &n, &start);

	while (1)
	{
		scanf("%d%d", &v1, &v2);
		if (v1 == -1 && v2 == -1) break; // -1과 -1이 입력되면 무한 루프 탈출
		map[v1][v2] = map[v2][v1] = 1; // 정점 v1과 정점 v2가 연결되었다고 표시
	}
	DFS(start); // DFS 시작!

	return 0;
}

결과:

8 1
1 2 1 3 2 4 2 5 4 8 5 8 3 6 3 7 6 8 7 8 -1 -1
1에서 2로 이동
2에서 4로 이동
4에서 8로 이동
8에서 5로 이동
8에서 6로 이동
6에서 3로 이동
3에서 7로 이동

위 코드에 주석으로 모두 표시해 두었으니, 이해가 되지 않는 부분은 참고하시면 되겠네요. 결과에서 입력되는 데이터가 너무 길어서 한줄로 작성했습니다. 혹시 시간이 나시는 분들은, 트리나 그래프 자료구조를 이용하여 DFS 알고리즘을 구현해보세요. 상당히 도움이 많이 될것이라고 생각합니다.

다음으로는, DFS를 통해 최단 경로의 길이를 구하는 코드를 구현해보도록 합시다. 그러기 전에, 어떻게 구현해야 할지 생각을 해보아야 겠죠?

깊이 우선 탐색(DFS)를 통한 최단 경로 길이 구하기 설계

아래 그림의 도로에서 최단 경로의 길이를 구하는 알고리즘을 설계해보도록 합시다.

위 그림을 보시면 S는 시작(Start) 지점이고, F는 도착(Final) 지점으로, 시작점에서 도착점까지 최단 경로의 길이를 구하는 것을 DFS를 통해 구해봅시다. 그리고 이미 알고계시겠지만, 흰색 칸은 이동할 수 있는 지점, 회색 칸은 이동할 수 없는 지점입니다. 자, 그럼 시작해보도록 합시다.

모든 경로의 길이를 구하자면 위 그림과 같습니다. 경로의 길이가 9인 지점에서 두 갈래의 길로 나뉘는데, 지름길을 통하면 도착점까지의 길이가 13이 되고, 먼 길을 통해 간다면 길이가 17이 됨을 알 수 있습니다. 이를 코드로 구현한다면, 위 도로는 2차원 배열을 통해 만들 수 있고 지나갈 수 있는 길은 1로, 지나갈 수 없는 길은 0으로 표시하시면 됩니다.

그리고 DFS를 통해 지나다닌 길은 이미 방문했다는걸 알려주기 위해 0으로 표시했다가, 도착점에 도착하면 모두 1로 되돌려 주시면 됩니다. 이동할때는 배열의 범위를 넘어섰는지, 어떤 길은 막혀있으므로 가면 안된다는지는 모두 체크해 주어야 겠죠? 그럼 이제는, 코드로 이를 한번 구현해보도록 합시다.

깊이 우선 탐색(DFS)를 통한 최단 경로 길이 구하기 구현

우선 길이가 N으로 주어지면, 크기가 N*N인 2차원 배열을 만들도록 합시다. 이번에도 역시 재귀 호출로 구현하고, DFS 함수에 좌표를 나타내는 x와 y와 길이를 나타내는 l을 매개변수에 넣도록 합시다. 이제, 코드로 구현해보도록 합시다.

#include <stdio.h>

int n, min; // 맵의 크기와 최소값을 나타내는 변수
int map[10][10]; // 맵을 나타내는 2차원 배열

void DFS(int x, int y, int l)
{
	// 도착 지점에 도착했을 경우
	if (x == n - 1 && y == n - 1)
	{
		// 현재 최소값이 l보다 크면, l이 작은 것이므로 l를 최소값으로 지정
		if (min > l) min = l;
		return;
	}
	map[y][x] = 0; // 방문했음을 표시하기 위해 0을 대입

	// 위로 이동할 수 있다면 이동!
	if (y > 0 && map[y - 1][x] != 0) DFS(x, y - 1, l + 1);
	// 아래로 이동할 수 있다면 이동!
	if (y < n - 1 && map[y + 1][x] != 0) DFS(x, y + 1, l + 1);
	// 왼쪽으로 이동할 수 있다면 이동!
	if (x > 0 && map[y][x - 1] != 0) DFS(x - 1, y, l + 1);
	// 오른쪽으로 이동할 수 있다면 이동!
	if (x < n - 1 && map[y][x + 1] != 0) DFS(x + 1, y, l + 1);

	map[y][x] = 1; // 지나간 자리를 원상태로 되돌리기 위해 1을 대입
}

int main()
{
	int i, j;

	scanf("%d", &n);
	min = n * n; // 모든 경로를 돌아다녀도 n * n이니, 이를 최소값으로 지정해둔다
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			scanf("%d", &map[i][j]);
	DFS(0, 0, 1); // DFS 시작!

	printf("최단 거리: %d\n", min);

	return 0;
}

결과:

5
1 1 1 1 1
0 0 0 0 1
1 1 1 1 1
1 0 1 0 0
1 1 1 1 1
최단 거리: 13

위 코드에서 설명이 필요한 부분은 모두 주석으로 추가 설명을 달았습니다. 이것도 시간 나시는 분들은 트리 혹은 그래프 자료구조를 이용해서 구현해보세요. 최대한 잘 설명해보려고 해도, 지식 부족인지 더 자세히 설명할 수가 없네요. 여기까지 봐주신 분들에게 모두 수고하셨고 감사하다는 말을 전해드리고 싶습니다. DFS에 관한 설명은 우선 여기에서 그만 마치도록 하겠습니다. 다음 강좌에서는 너비 우선 탐색(BFS, Breath First Search)에 대해 알아보도록 하겠습니다.