[JAVA(자바)] 깊이 우선 탐색(DFS)

그래프에서 모든 정점을 방문하는 방법에는 대표적으로 두가지가 있다.

1. 너비 우선 탐색(BFS: breath-first Search)

2. 깊이 우선 탐색 (DFS: depth-first search)

오늘은 깊이 우선 탐색에 대해 공부하고자 한다.

---

깊이 우선 탐색 : 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른방향으로 다시 탐색을진행한다.

<DFS 알고리즘>
dfs(v){
    v를 방문했다고 표시;
    for all u ∈ (v에 인접한 정점) do
       if(u가 아직 방문하지 않았다면)
            then dfs(u)
}

---

<DFS 방법>

dfs

그림과 같은 그래프가 있다. 시작 지점은 1이라고 하자.

(여기서 갈래가 두개 이상이라면 가장 작은 수를 선택한다.)

 

*한방향으로 갈 수 있을 때까지 가면 다음과 같은 그림이 나온다.

dfs

위 그림과 같이 1 → 2 → 4 → 8 → 6 → 3 까지 갈 수 있다. 하지만 그 이후로 문제가 생긴다.

dfs

3에서 가던길 그대로 가면 1이 되지만 1은 이미 방문한 노드이기 때문에 갈 수 없다.

그렇다면 3의 다른 갈림길이 7로 이동하여 다시 탐색을 시작해주면된다. 

 

이러한 알고리즘을 코드로 바꿔보면 다음과 같다.

---

import java.util.Scanner;
 
class Solution {
 
    static final int MAX_VERTEX = 30;
 
    static int vertex;
    static int map[][] = new int[MAX_VERTEX][MAX_VERTEX];
    static int visit[] = new int[MAX_VERTEX];
 
    static void depthFirstSearch(int v)
    {
        visit[v] = 1;
        for (int i = 1; i <= vertex; i++)
        {
            if (map[v][i] == 1 && visit[i] == 0)
            {
                System.out.printf("%d ", i);
                depthFirstSearch(i);
            }
        }
    }
 
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt();
 
        for (int test_case = 1; test_case <= T; test_case++)
        {
            vertex = sc.nextInt();
            int start = sc.nextInt();
 
            map = new int[MAX_VERTEX][MAX_VERTEX];
            visit = new int[MAX_VERTEX];
             
            while (true)
            {
                int v1 = sc.nextInt();
                int v2 = sc.nextInt();
                if (v1 == -1 && v2 == -1)
                {
                    break;
                }
                map[v1][v2] = map[v2][v1] = 1;
            }
            System.out.printf("#%d ", test_case);
            System.out.printf("%d ", start);
            depthFirstSearch(start);
            System.out.printf("\n");
        }
 
        sc.close();
    }
}

---

<코드 출처>
"SW Expert Academy", https://swexpertacademy.com/main/code/referenceCode/referenceCodeDetail.do?referenceId=DFS_SEARCHING&category=Algorithm&&