[Java] DFS 알고리즘

🧑🏻‍💻 DFS - 깊이 우선 탐색

• 재귀함수로 구현되며 스택구조를 가진다.
  • 한 번 방문한 노드는 다시 방문하지 않음
• 시간 복잡도는 O(V+E)로 노드 수 + 에지 수로 구한다.

문제

• 백준 11724
• 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static ArrayList<Integer>[] A; // 각 노드의 연결 노드 리스트 (자식노드)
    static Boolean visited[]; // 노드별 방문 여부 배열

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int n = Integer.parseInt(st.nextToken()); // 노드의 수
        int m = Integer.parseInt(st.nextToken()); // 에지의 수
        A = new ArrayList[n+1]; // 노드별 연결 노드 리스트 초기화
        visited = new Boolean[n + 1]; // 방문 여부 배열 초기화
        Arrays.fill(visited, false); // 모든 방문 배열 false로 입력

        for (int i = 1; i < n + 1; i++) {
            A[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < m; i++) { // 모든 노드 리스트에 연결된 자식 노드 입력
            st = new StringTokenizer(bf.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            A[s].add(e);
            A[e].add(s);
        }

        int count = 0;
        for (int i = 1; i < n + 1; i++) { // 모든 노드에 대해 반복
            if (!visited[i]) { // 기본 값이 false 이기에, 방문하지 않았다면 -> false이니까 조건문이 작동하려면 !visited 를한다.
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
    }

    static void DFS(int v) {
        if (visited[v]) {
            return;
        }
        visited[v] = true;
        for (int i : A[v]) {
            if (visited[i] == false) {
                DFS(i);
            }
        }
    }
}

• !visited[i] 부분이 처음에 계속 이해가 되지 않았다. visited 는 false로 초기화 되었는데, 왜 ‘방문하지 않았으면’ 의 조건이 !visited 가 되는지 이해가 안됐다. 결론적으로 알게된 건, ‘방문하지 않았으면, false’ 이기에 !으로 ‘true’ 를 만들어 주어 조건문이 실행되게 하기 위함이다.