[탐색 알고리즘 강좌]
해를 찾기위해 전진, 또 전진!
깊이 우선 탐색(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)에 대해 알아보도록 하겠습니다.
'수학 > 알고리즘, 자료구조' 카테고리의 다른 글
알고리즘 4-2강. 너비 우선 탐색(Breadth First Search) (20) | 2013.08.07 |
---|---|
알고리즘 4-1강. 깊이 우선 탐색(Depth First Search) (61) | 2013.08.05 |
알고리즘 3강. 탐욕 알고리즘(Greedy Algorithm) (4) | 2013.07.25 |
자료구조 5강. 힙(Heap) (4) | 2013.05.31 |
알고리즘 2-3강. 탐색 알고리즘 - 이진 탐색 트리(Binary Search Tree) (13) | 2013.05.28 |
알고리즘 2-2강. 탐색 알고리즘 - 이진 탐색(Binary Search) (10) | 2013.05.25 |
저기 위에 최단경로길이 구하는 코드에서 min값이 어디서 업데이트가 되는지요?
저 알고리즘은 weighted graph에서도 동일하게 사용이 가능할까요?
5까지 간 후에 직전노드로 회귀하는 것은 어떻게 작동하나요? if문에 속하지 않으면 어디로 이동하라는 명시가 안되어있는데..
좋은 강의 감사합니다.
그런데 위 DFS 코드는 재귀호출을 통한 백트레킹에 더 가까운거 아닌가요?
처음 입문하는지라 개념이 헷갈리네요.
감사합니다.
좋은글, 설명 도움이 많이 되었습니다.
광고 다시면 좋을것 같아요
방문자들이 보답으로 클릭하면 글게시한 노고에 조금이라도 보답이 되지않을까 합니다.
11111
10101
10101
10101
11101
의 구조라면 위->아래->왼쪽->오른쪽으로 재귀호출을 하기때문에
0,0에서 바로 오른쪽으로 직진하는것보다 돌아서 가기때문에 l이 최솟값이 아닌 상태이고, 이미 방문했기 때문에 최단 경로를 구할 수 없게 되는 것이 아닌가요?
최단거리 구할때 x,y좌표가 왜 [y][x]가 되는지 모르겠습니다. ㅜㅜ
간단히라도 설명해주실 분...
아파트 호수를 생각하세요. [층][호] 입니다.
위-아래-왼-오른 순서로 움직입니다.
1 2 3 4 5
6
9 8 7
10
11 12 13 (9에서 아래)
1 2 3 4 5
6
11 10 9 8 7
12 16
13 14 15 (9까지 돌아가서 왼, 15에서 위;도착할 수 없음)
1 2 3 4 5
6
11 10 9 8 7
12
13 14 15 16 17 (15까지 돌아가서 오른)
9에서 왼쪽, 아래쪽으로 갈 수 있어 경우의 수가 2가지 인데요
왜 결과값을 출력할때는 최단거리인 13만 출력되는 건가요?
왼쪽을 지나 올 경우 17이라는 거리값도 나오는데
왜 13만 출력되는지 궁금합니다. ㅠㅠ
그리고
map[y][x] = 1; // 지나간 자리를 원상태로 되돌리기 위해 1을 대입
이 부분이 무슨 역할을 하는지도 궁금합니다!
DFS 맨 첫줄에
if ((l+ n-1-x + n-1-y) >= min) return;
가지치기를 하시면 필요없는 재귀콜을 없앨수 있습니다
가지치기를 할 경우 불필요한 부분 재귀를 막을 수 있습니다.
따라서 9번째 노드에서 아래로 이동해서 계산된 min값에 의해 왼쪽이로 이동을 방지할 수 있습니다.
DFS + 가지치기 = 백트래킹 알고리즘 입니다.
신기해요
map[y][x] = 1; 하면서 이전위치 돌아가고 갓던곳은 다시 안가고 새로운 경로 찾으면서 가는게
레알 신기함
중단점으로 살펴봤는데
어떻게 X=1 Y=2 인 지점까지 왔을떄 IF문을 다 제치고 map[2][1] 값이 0에서 1로 다시 바뀌자나요
그 다음에 어떻게 x=0 y=2인 지점으로 다시 돌아가는건가요? x값을 줄인다는 커맨드도 없는데 좌표가
이전 위치로 돌아가는 이유가 먼가요??
dfs 개념 코드 있잖아요 제가 동적 할당을 해서 만들어보려고 했는데 그냥 보기만 하고 만들어보니 안되더라구요.. visited를 초기화해야되는걸 잊고 그냥 했더니 안되서... 혼란을 줄이기 위해 visited 배열을 초기화 하는거 어떤가요
map[y][x] = 1; // 지나간 자리를 원상태로 되돌리기 위해 1을 대입
여기 최단경로구하는 예제에서는 위의 코드가 없어도 잘돌아가는데 꼭넣어야되나요?
정말 감사합니다! 기초를 잘 잡게 해주시네요!! ㅎㅎ
경로 길이가 9인 지점에서 두갈레로 길이 나뉘는데 if문 두개를 동시에 재귀함수 호출하는 건가요?
짜여진 코드 보면 아래로 이동하는 if문 먼저 나와서 재귀함수가 호출되면 l과 min은 13이고 끝나게 되는데 그럼 왼쪽으로 이동하는 건 l이 13으로 이미 지정되어 있는 게 아닌가요? 다시 l은 9인건가요?
트리로 구현할 경우 알고리즘을 간단하게 알려주실 수 있나요?
실제 알고리즘 대회에서는 사용 못할듯....
map크기가 500*500정도만 되도 timeout다 걸릴듯....BSF로 수행해야 할듯...