[Java] 깊이 우선 탐색(DFS)

🔎DFS

DFS는 Depth First Search의 약자로, 깊이 우선 탐색이라고도 부르며 그래프 순회 방법 중 하나이다.

순회 방식은, 시작 노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우, 이전 노드로 돌아가서, 다시 깊이 우선 탐색을 반복하는 방식이다.

🔎탐색 과정

위의 그래프를 예를 들어 DFS 탐색을 시작해보겠다.

• 우선 1번 노드를 방문하고 출력한다. (탐색 순서 : 1)
• 이제 1번 노드에 인접한 노드인 2번, 3번, 8번 중 하나를 방문해야 하는데, 오름차순으로 방문하기로 가정해보겠다.
• 따라서 2번 노드를 방문하고 출력한다. (탐색 순서 : 1 → 2)
• 2번 노드에 인접한 노드는 6번, 8번이 있는데, 오름차순 기준이기 때문에 6번 노드로 이동한다.
• 6번 노드를 방문하고 출력한다. (탐색 순서 : 1 → 2 → 6)
• 6번 노드에 인접한 노드는 2번 노드 뿐인데, 이미 방문을 하였으므로 더 이상 방문하지 않고 6번 노드를 호출한 이전 노드(2번 노드)로 다시 돌아간다.
• 2번 노드에 인접한 노드 중 8번 노드가 남아있으므로 8번 노드로 이동한다.
• 8번 노드를 방문하고 출력한다. (탐색 순서 : 1 → 2 → 6 → 8)
• 8번 노드에 인접한 노드는 1번과 2번 노드인데, 둘 다 이미 방문하였으므로 더 이상 방문하지 않고 8번을 호출한 노드(2번 노드)로 돌아간다.
• 2번 노드에 인접한 6번, 8번 노드를 이미 다 방문하였으므로 2번 노드를 호출한 1번 노드로 돌아간다.
• 이제, 1번 노드에 인접한 노드 중 방문하지 않은 노드인 3번 노드로 이동한다.
• 3번 노드를 방문하고 출력한다. (탐색 순서 : 1 → 2 → 6 → 8 → 3)
• 3번 노드에 연결된 노드는 5번 노드 뿐이므로 5번 노드를 방문 후 출력한다. (탐색 순서 : 1 → 2 → 6 → 8 → 3 → 5)
• 5번 노드에 연결된 노드는 4번, 7번 노드인데, 오름차순 기준이니 4번 노드를 먼저 방문 후 출력한다. (탐색 순서 : 1 → 2 → 6 → 8 → 3 → 5 → 4)
• 마지막으로 남은 7번 노드를 방문 후 출력하면 더 이상 방문할 노드가 없으므로 탐색이 종료된다.

최종적인 탐색 순서는 다음과 같다.
(탐색 순서 : 1 → 2 → 6 → 8 → 3 → 5 → 4 → 7)

🤔장단점

장점

• 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다.

🖥️구현

DFS를 코드로 구현하는 방법은 재귀로 구현하는 방법과 Stack을 사용해서 구현하는 방법 2가지가 있다.

일반적으로, Stack 보다는 재귀로 구현하는 게 코드가 더 짧고 간결하기 때문에, 재귀로 많이 구현을 한다.

재귀(Recursion) 형태로 구현

import java.util.*;

public class Main {
    static int edge; // 간선의 수
    static int vertex; // 정점의 수
    static int[][] map; // 정점 간의 연결의 정보를 담는 객체
    static boolean[] visit; // 정점을 방문했는지 체크하기 위한 객체

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        vertex = sc.nextInt();
        edge = sc.nextInt();
        map = new int[vertex + 1][vertex + 1];
        visit = new boolean[vertex + 1];

        for (int i = 0; i < edge; i++) {
            int start = sc.nextInt();
            int next = sc.nextInt();

            map[start][next] = 1;
            map[next][start] = 1;
        }
        dfs(1);
    }

    public static void dfs(int start) {
        visit[start] = true;
        System.out.println(start + " ");

        for (int i = 1; i < vertex + 1; i++) {
            if (map[start][i] == 1 && visit[i] == false) {
                dfs(i);
            }
        }
    }
}