[Java] - DFS

2023년 04월 13일

테스트 환경

🛠️ Java : Amazon corretto 17

DFS(Depth-First Search)란?

해석 그대로 깊이를 우선으로 탐색하는 알고리즘이다.
DFS 알고리즘은 주로 최적의 해를 구하는 것이 아닌 모든 노드를 탐색하며, 경우를 찾는 용도로 사용된다.

모든 노드를 방문해야할 경우

시작점에서 목적지까지 중복되는 숫자가 있으면 안 될 경우

경로마다 특징을 저장해둬야하는 경우

쉽게 이해하기 위해 아래 사진을 통해 확인해보자!

해당 설명은 오름차순 방문을 기준입니다.

0번 노드 방문 후 visited 체크
- 인접 노드 : 1, 2번
- 1번 노드로 탐색(오름차순 기준)
1번 노드 방문 후 visited 체크
- 인접 노드 : 3, 4번
- 3번 노드로 탐색(오름차순 기준)
3번 노드 방문 후 visited 체크
- 인접 노드 : 1, 4번
- 1번 노드는 방문했기 때문에 4번 노드 방문
4번 노드 방문 후 visited 체크
- 인접 노드 : 1, 3번
- 인접해 있는 모든 노드를 방문한 상태
- 1번 ➡ 0번 ➡ 2번 노드 방문
2번 노드 방문 후 visited 체크
- 인접 노드 : 5, 6번
- 5번 노드로 탐색(오름차순 기준)
2번 노드 방문 후 visited 체크
- 인접 노드 : 2, 6번
- 2번 노드는 방문했기 때문에 6번 노드 방문
모든 노드 방문을 했기 때문에 종료

구현

실제 문제를 통해 DFS에 대해서 알아보자!

백준 - DFS와 BFS
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
# input
4 5 1
1 2
1 3
1 4
2 4
3 4

# output
1 2 4 3

현재 포스트는 DFS에 대한 코드만 사용합니다.

해설

1번 노드는 2, 3, 4번과 연결되어 있다.
2번 노드는 4번과 연결되어 있다.
3번 노드는 4번과 연결되어 있다.

1번 노드 ➡ 2번 노드(가장 인접하고 정점 번호가 작음)
2번 노드 ➡ 4번 노드(가장 인접하고 정점 번호가 작음)
4번 노드 ➡ 3번 노드(가장 인접하고 정점 번호가 작음)

해당 그림을 인접 행렬로 나타내면 아래와 같다.

구분	1	2	3	4
1	0	`1`	1	1
2	1	0	0	`1`
3	1	0	0	1
4	1	1	`1`	0

Recursion

public class DFS_1260 {
    public static boolean[] visited;
    public static int[][] graph;
    public static int N, M, V;

    public static void main(String[] args) throws IOException {
        // 첫 줄 입력 받는 과정
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        // 받은 정보를 토대로 그래프 초기화하는 과정
        visited = new boolean[N + 1];
        graph = new int[N + 1][N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 인접 행렬 생성
            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        // V(시작할 정점)부터 탐색
        dfs(V);
    }

    public static void dfs(int point) {
        // 현재 노드 방문 처리 및 출력
        visited[point] = true;
        System.out.print(point + " ");

        // 현재 정점이 그래프 크기(끝 지점)와 같다면 종료
        if (point == graph.length) {
            return;
        }

        for (int i = 1; i < graph.length; i++) {
            // 인접 행렬이 존재하고, 방문하지 않은 곳이라면 DFS 진행
            if (graph[point][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }

    }
}

Stack

public class DFS_1260 {
    public static boolean[] visited;
    public static int[][] graph;
    public static int N, M, V;
    public static Stack<Integer> stack = new Stack<>();

    public static void main(String[] args) throws IOException {
        // 첫 줄 입력 받는 과정
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        // 받은 정보를 토대로 그래프 초기화하는 과정
        visited = new boolean[N + 1];
        graph = new int[N + 1][N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 인접 행렬 생성
            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        // V(시작할 정점)부터 탐색
        dfs(V);
    }
    private static void dfs(int point){
      // 그래프의 끝 지점
      int n = graph.length - 1;

      // 스택에 시작 지점을 넣고, 방문 처리
      stack.push(point);
      visited[point] = true;
      System.out.print(point + " ");

      // 스택이 비어있을 때까지 반복
      while (!stack.isEmpty()) {
        int peek = stack.peek();
        boolean flag = false;

        // 현재 노드와 인접하고, 방문하지 않은 노드 탐색
        for (int i = 1; i <= n; i++) {
          if (graph[peek][i] == 1 && !visited[i]) {
            // 스택에 추가 후 방문 처리
            stack.push(i);
            System.out.print(i + " ");

            visited[i] = true;
            flag = true;
            break;
          }
        }
        if (!flag) {
          stack.pop();
        }
      }
    }
}

🤔 회고

두 방법으로 모두 풀이하면서, 재귀를 통한 풀이가 훨씬 풀기 편하다는 것을 알 수 있었다.

Jwhy