Media Log

[탐색 알고리즘 강좌]


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

깊이 우선 탐색(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)에 대해 알아보도록 하겠습니다.

  1. 이전 댓글 더보기
  2. 코드비기너 at 2016.09.07 21:32 신고 [edit/del]

    저기 위에 최단경로길이 구하는 코드에서 min값이 어디서 업데이트가 되는지요?
    저 알고리즘은 weighted graph에서도 동일하게 사용이 가능할까요?

    Reply
    • stoad at 2016.10.13 15:57 신고 [edit/del]

      최솟 값은 마지막 위치에 도달았을때, DFS 몇번을 거쳐서 실행됬는지에 따라 초기화 되는 것 같네요.

    • LHJ at 2017.02.28 12:07 신고 [edit/del]

      코드를 보시면 목적지에 도착하면
      min값을 재설정 하는것을 보실 수 있습니다. 잘못보시면 min = 1을 대입하시는걸로 착각하실 수도 있습니다.
      재귀호출을 하면서 알파벳 l에 l+1을 해주시는것을 볼 수 있습니다! 도착했을 때 min값을 l로 갱신시켜줍니다.

  3. kim at 2016.10.15 21:32 신고 [edit/del]

    5까지 간 후에 직전노드로 회귀하는 것은 어떻게 작동하나요? if문에 속하지 않으면 어디로 이동하라는 명시가 안되어있는데..

    Reply
  4. Nam at 2016.11.29 17:38 신고 [edit/del]

    좋은 강의 감사합니다.
    그런데 위 DFS 코드는 재귀호출을 통한 백트레킹에 더 가까운거 아닌가요?
    처음 입문하는지라 개념이 헷갈리네요.

    Reply
  5. 방문자 at 2017.01.24 14:05 신고 [edit/del]

    감사합니다.
    좋은글, 설명 도움이 많이 되었습니다.

    광고 다시면 좋을것 같아요
    방문자들이 보답으로 클릭하면 글게시한 노고에 조금이라도 보답이 되지않을까 합니다.

    Reply
  6. 완전초보 at 2017.03.20 15:27 신고 [edit/del]

    11111
    10101
    10101
    10101
    11101
    의 구조라면 위->아래->왼쪽->오른쪽으로 재귀호출을 하기때문에

    0,0에서 바로 오른쪽으로 직진하는것보다 돌아서 가기때문에 l이 최솟값이 아닌 상태이고, 이미 방문했기 때문에 최단 경로를 구할 수 없게 되는 것이 아닌가요?

    Reply
  7. 모르겠어요 at 2017.03.22 01:43 신고 [edit/del]

    최단거리 구할때 x,y좌표가 왜 [y][x]가 되는지 모르겠습니다. ㅜㅜ
    간단히라도 설명해주실 분...

    Reply
    • 이윤주 at 2018.06.14 19:18 신고 [edit/del]

      코딩 스타일입니다.
      모르겠어요 님 말처럼 구현하시려면

      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[x][y] = 0; // 방문했음을 표시하기 위해 0을 대입

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

      map[x][y] = 1; // 지나간 자리를 원상태로 되돌리기 위해 1을 대입
      }
      이렇게 구현하시면 됩니다.

  8. C at 2017.03.24 12:00 신고 [edit/del]

    아파트 호수를 생각하세요. [층][호] 입니다.

    Reply
  9. C at 2017.03.24 12:10 신고 [edit/del]

    위-아래-왼-오른 순서로 움직입니다.
    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까지 돌아가서 오른)

    Reply
    • C at 2017.03.24 12:14 신고 [edit/del]

      글이 깨지네요.

      위-아래-왼-오른 순서로 움직입니다.
      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까지 돌아가서 오른)

  10. 궁그미 at 2017.03.25 16:58 신고 [edit/del]

    9에서 왼쪽, 아래쪽으로 갈 수 있어 경우의 수가 2가지 인데요
    왜 결과값을 출력할때는 최단거리인 13만 출력되는 건가요?
    왼쪽을 지나 올 경우 17이라는 거리값도 나오는데
    왜 13만 출력되는지 궁금합니다. ㅠㅠ

    그리고
    map[y][x] = 1; // 지나간 자리를 원상태로 되돌리기 위해 1을 대입
    이 부분이 무슨 역할을 하는지도 궁금합니다!

    Reply
    • 나비야 at 2017.05.24 10:05 신고 [edit/del]

      경로는 수백가지라도 결국 각 경로마다 거리가 있을거고 그 거리중에 제일 작은값만 min 값에 갱신시키며 최소값을 유지하는거죠.
      DFS 함수를 타고 들어오다 보니 현재 위치를 2,2 라고 해보시죠. 그런데 2, 2 는 좌측에서도 들어왔을 수도 있고 위쪽에서도 들어왔을 수 있습니다. 그런데 좌측을 통해 들어왔다고 막아놓고 방치해버리면 추후 위쪽을 통해 들어오는 경로는 탐색을 안하는 문제가 발생할 수 있겠죠. 그렇기 때문에 좌측방향에서 들어와서 탐색을 마쳤을 경우 다른 방향에서 들어와 탐색을 허용하기 위해 해당 자리는 다시 초기화 해줘야 합니다.

  11. 딩굴댕굴 at 2017.07.20 16:47 신고 [edit/del]

    DFS 맨 첫줄에
    if ((l+ n-1-x + n-1-y) >= min) return;
    가지치기를 하시면 필요없는 재귀콜을 없앨수 있습니다

    Reply
    • 생초보 at 2017.08.11 05:16 신고 [edit/del]

      필요없는 재귀콜을 없앨수 있다는 말씀이 위,아래,왼,오 에 해당하는 재귀콜을 다 없앨수 있다는 말씀이신가요 ??

  12. aQua! at 2017.08.13 12:13 신고 [edit/del]

    가지치기를 할 경우 불필요한 부분 재귀를 막을 수 있습니다.
    따라서 9번째 노드에서 아래로 이동해서 계산된 min값에 의해 왼쪽이로 이동을 방지할 수 있습니다.

    Reply
  13. aQua! at 2017.08.13 12:16 신고 [edit/del]

    DFS + 가지치기 = 백트래킹 알고리즘 입니다.

    Reply
  14. 신기해 at 2017.10.27 18:17 신고 [edit/del]

    신기해요
    map[y][x] = 1; 하면서 이전위치 돌아가고 갓던곳은 다시 안가고 새로운 경로 찾으면서 가는게
    레알 신기함

    Reply
  15. 질문이요 at 2017.11.10 00:30 신고 [edit/del]

    중단점으로 살펴봤는데
    어떻게 X=1 Y=2 인 지점까지 왔을떄 IF문을 다 제치고 map[2][1] 값이 0에서 1로 다시 바뀌자나요
    그 다음에 어떻게 x=0 y=2인 지점으로 다시 돌아가는건가요? x값을 줄인다는 커맨드도 없는데 좌표가
    이전 위치로 돌아가는 이유가 먼가요??

    Reply
    • BlogIcon EXYNOA at 2017.11.10 05:27 신고 [edit/del]

      (1, 2)까지 온 시점에서 왼쪽으로만 이동할 수 있으므로 아래의 코드가 실행되는 것입니다.
      f (x > 0 && map[y][x - 1] != 0) DFS(x - 1, y, l + 1);

    • 질문 at 2017.11.10 10:22 신고 [edit/del]

      음 왼쪽으로만 이동할수 있다는게..이해가 안되요 x=1 y=2인 지점이 1이 된다음에
      왼쪽으로 이동할수 있으려면
      x=0 y=2 인 자리는 1,2에 오기전에
      방문한 지점이니깐 0으로 변해서
      f (x > 0 && map[y][x - 1] != 0) DFS(x - 1, y, l + 1);
      이 조건문에서 map[y=2][1-1] =0이니깐
      0이 아닐떄만 참이니깐 조건문식이false되서 이동을 못하지 않나요..

    • BlogIcon EXYNOA at 2017.11.10 12:20 신고 [edit/del]

      아래 코드에서 지나간 구간은 다시 0에서 1로 되돌리게 됩니다.

      map[y][x] = 1;

      (1) (2, 4)에서 왼쪽으로 진행 후 막힌 것을 확인하고, 지나왔던 길을 모두 1로 되돌립니다.
      (2) (2, 4)로 돌아와 오른쪽으로 이동할 수 있으므로, 오른쪽으로 진행하여 도착 지점을 찾습니다.
      (3) 그리고 (1, 2)로 돌아와 이쪽으로 진행했을 때의 최소값도 구하게 됩니다.

      불필요한 탐색을 수행하기 때문에 최적의 값을 더이상 갱신할 수 없다면 가지치기를 통해 나머지 상태 공간은 살피지 않도록 해야 합니다.

      추신. 4년 전에 작성한 글이라, 알고리즘이나 자료구조도 새롭게 써야할 것 같은데 시간이 좀처럼 나질 않네요. =_=);

  16. 허허 at 2017.11.30 18:41 신고 [edit/del]

    dfs 개념 코드 있잖아요 제가 동적 할당을 해서 만들어보려고 했는데 그냥 보기만 하고 만들어보니 안되더라구요.. visited를 초기화해야되는걸 잊고 그냥 했더니 안되서... 혼란을 줄이기 위해 visited 배열을 초기화 하는거 어떤가요

    Reply
  17. ㅣㅗ히힣 at 2018.01.26 16:31 신고 [edit/del]

    map[y][x] = 1; // 지나간 자리를 원상태로 되돌리기 위해 1을 대입
    여기 최단경로구하는 예제에서는 위의 코드가 없어도 잘돌아가는데 꼭넣어야되나요?

    Reply
  18. SW at 2018.03.25 14:37 신고 [edit/del]

    정말 감사합니다! 기초를 잘 잡게 해주시네요!! ㅎㅎ

    Reply
  19. 12 at 2018.04.10 16:59 신고 [edit/del]

    경로 길이가 9인 지점에서 두갈레로 길이 나뉘는데 if문 두개를 동시에 재귀함수 호출하는 건가요?
    짜여진 코드 보면 아래로 이동하는 if문 먼저 나와서 재귀함수가 호출되면 l과 min은 13이고 끝나게 되는데 그럼 왼쪽으로 이동하는 건 l이 13으로 이미 지정되어 있는 게 아닌가요? 다시 l은 9인건가요?

    Reply
  20. QQQQQ at 2018.05.17 23:24 신고 [edit/del]

    트리로 구현할 경우 알고리즘을 간단하게 알려주실 수 있나요?

    Reply
  21. KOOOO at 2018.10.05 22:22 신고 [edit/del]

    실제 알고리즘 대회에서는 사용 못할듯....
    map크기가 500*500정도만 되도 timeout다 걸릴듯....BSF로 수행해야 할듯...

    Reply

submit

티스토리 툴바