[Algorithm] DFS 깊이탐색

안녕하세요. 림키입니다. 오랜만에 글을 쓰네요.. 요새 너무 바뻐서 ㅠㅠ...

이번 시간은 그래프를 탐색하는 방법 중 하나인 깊이탐색 DFS(Depth First Search)에 대해서 알아보도록 하겠습니다.

깊이탐색 DFS(Depth First Search)은 저장된 그래프의 모든 정점을 1번 방문하는 방법 중 하나입니다.  깊이탐색 DFS(Depth First Search)은 스택을 이용하며, 갈 수 있는 만큼 최대한 많이 가고 갈 수 없을 경우 이전 정점으로 돌아가서 다시 탐색을 하는 녀석입니다. 

저는 먼저 코드를 바탕으로 설명을 하고자 합니다. 다른 블로그에는 설명 이후 코드를 하지만 반대로 해볼까 합니다.

그래프를 저장하는 방법에는 크게 3가지가 있습니다. 인접행렬, 인접리스트, 간선리스트.. 저는 그중 가장 많이 사용하는 인접리스트를 기반으로 설명하겠습니다.

DFS.java

package GraphSearching;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class DFS {

	static ArrayList<Integer>[] a;
	static boolean[] visit;
	
	public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();	//정점의 수
        int m = sc.nextInt();	//간선의 수
        int start = sc.nextInt();//시작할 정점

        a = new ArrayList[n+1];		//인덱스 편의상 n+1를 하고, 0번째 요소는 사용하지 않음
        visit = new boolean[n+1];	//인덱스 편의상 n+1를 하고, 0번째 요소는 사용하지 않음
        
        for (int i=1; i<=n; i++) {
            a[i] = new ArrayList<Integer>();
        }

        for (int i=0; i<m; i++) {
            int u = sc.nextInt();	//간선으로 이어진 정점1
            int v = sc.nextInt();	//정점1과 간선으로 이어진 정점2
            //양뱡향일 경우 양쪽다 저장해준다.
            a[u].add(v);
            a[v].add(u);
        }

      
        dfs(start);
        
        System.out.println("");
        System.out.println("a : "+Arrays.toString(a));
        System.out.println("visit : "+Arrays.toString(visit));
    }
	
	
	public static void dfs(int x) {
   
        visit[x] = true;
        System.out.print(x + " ");
        
        for (int y : a[x]) {
            if (visit[y] == false) {
                dfs(y);
            }
        }
    }
	
	
	

}

자 위 코드를 기반으로 깊이 탐색을 해보겠습니다. 

입력 첫줄에는 정점의 개수, 간선의 개수, 탐색을 시작할 정점 이 3가지를 입력받고

나머지 2~5번째 줄은 간선과 연결된 정점들을 입력합니다.

입력값 

5 4 5

5 4

4 3

4 2

1 5

출력 값에서는 깊이 탐색된 순서가 출력되고, 확인 간선의 정보를 담고있는 a 와 방문 여부를 담고있는 visit 을 확인 할 수 있는데 각 a, visit의 첫번째 요소는 인덱스 편의상 0번 첨자이기 때문에 무시하셔도 됩니다. 아무튼 잘 탐색이 되면 visit은 1~5번 요소는 true가 되어야 합니다.

출력값

5 4 3 2 1 

a : [null, [5], [4], [4], [5, 3, 2], [4, 1]]

visit : [false, true, true, true, true, true]

이제 그림을 보면서 동작 하나하나를 확인해봅시다.

그림에서 보듯이 a 라는 변수에는 ArrayList로 각 정점이 간선으로 연결된 정점들이 누구인지 정보를 담고 있습니다. 예를 들어 a[1] 은 1정점을 나타내고 1정점은 5정점과 간선으로 연결되어 있기 때문에 a[1] 요소의 값은 5를 담고 있는 ArrayList가 있습니다. 또 a[4] 은 4정점을 나타내고, 4정점은 3정점,2정점,5정점으로 연결되어 있기 때문에 a[4] 요소에는 5,2,3 을 담고 있는 ArrayList가 있습니다. 

한가지 알아두어야 할 것은 깊이 탐색이 만약 5정점에서 시작할 경우 1정점으로 먼저갈지 5정점으로 먼저갈지는 상관이 없습니다. 그 기준은 우리가 정하면 됩니다. 보통 가야할 정점들 중 가장 값이 작은 정점으로 가지만 위 코드는 그런 로직이 따로 없으며, 사용자가 입력한 순서에 따라 깊이탐색을 하고 있음을 알 수 있습니다.

끝으로 vistit은 정점을 탐색했는지 여부에 대한 정보를 담고 있습니다. 별도의 초기화를 하지 않은 이상 모두 false로 초기화되어 있음을 확인할 수 있습니다. 또한, 스택을 사용한다고 했는데 자세히 보면 코드에는 스택이 없습니다. 그 이윤 재귀적인 함수 호출을 하기 때문에 스택과 같은 효과가 납니다. 따라서 스택을 별도로 사용하지 않고 재귀호출로 스택효과를 내는 것입니다. 

자 첫번째 시작 할 정점을 5정점으로 했기 때문에 5정점이 탐색되고, visit[5]는 true로 바뀝니다. 다음 간선을 등록한 순서대로 다음 탐색을 하기 때문에 1정점이 아닌 4정점으로 탐색을 할 것입니다.

4정점을 탐색하고 visit[4] 은 true를 표시합니다. 이제 4정점은 2정점,3정점 중에 탐색을 해야합니다. 역시 간선을 먼저 3정점과 4정점 정보를 입력했기 때문에 3정점을 탐색합니다.

이제 3정점을 탐색했고, visit[3]은 true로 바뀝니다. 이제 3정점이 연결된 정점은 4정점이 있습니다. 하지만 4정점은 이미 방문했기 때문에 탐색을 종료하고( visit[4]=true ), 이전 탐색 정점이었던 4정점으로 회귀합니다.

이제 4정점과 연결된 3정점은 이미 일전에 탐색했기 때문에 2정점으로 탐색을 합니다. 이런식으로 계속 깊이 탐색을 합니다.

모든 탐색이 종료되고, 지금까지 방문된 출력을 확인하면 5 - 4 - 3 - 2 - 1 임을 알 수 있습니다.

만약 입력할 시 간선의 정보입력 순서를 바꾸면 출력결과가 달라 질 수 있습니다.  그 이유는 아까 설명 드렸지만, 먼저 입력한 간선을 우선순위로 깊이탐색을 했기 때문입니다. 보통의 경우 탐색해야할 간선 중 가장 작거나 가장 큰 정점에게 우선 탐색할 우선권을 주는 것으로 구현되어 있을 것입니다.  다음 시간에는 너비 탐색에 대해서 알아보도록 하겠습니다.