[백준] S2 11724번 연결 요소의 개수 (Java)

https://www.acmicpc.net/problem/11724

해당 문제는 'Do it! 알고리즘 코딩테스트 자바 편'을 보면서 공부한 내용입니다.

👉 문제

연결 요소의 개수를 출력하라는 뜻은 예를 들어, 노드가 1-2-5 / 3-4-6 이렇게 연결되어 있다면 연결 요소 개수는 2개이고, 1-2-3-4-5-6 이런식으로 연결되어 있다면 연결 요소 개수는 1개라는 의미이다.

즉, 연결 요소는 에지(간선)로 연결된 노드의 집합이며, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판다할 수 있습니다. 입력1에 대해 과정을 설명하자면

1. 그래프를 인접 리스트로 저장하고 방문 배열도 초기화합니다. 방향이 없는 그래프이기 때문에 양쪽 방향으로 에지를 모두 저장합니다.
   인접 리스트
   1 -> 2,5
   2 -> 1,5
   3 -> 4
   4 -> 3,6
   5 -> 2,1
   6 -> 4
   방문 배열
   [1 2 3 4 5 6]
   [F F F F F F]

2. 1을 시작접으로 했을 때, 탐색을 마친 이후 방문한 곳은 1, 2, 5 이므로 방문 배열도 T로 바뀝니다.

   방문 배열
   [1 2 3 4 5 6]
   [T T F F T F]

3. 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행합니다. 예제 입력1의 경우 3, 4, 6 순서로 탐색을 마친 후 모든 노드를 방문했으니 전체 탐색이 종료됩니다.

   방문 배열
   [1 2 3 4 5 6]
   [T T T T T T]

4. 1~3의 과정을 통해 총 2번의 DFS가 진행되었다는 것을 알 수 있습니다. 즉, 연결 요소 개수는 2개 입니다!

👉 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class P11724_연결요소의개수_1 {
    static ArrayList<Integer>[] arr;    // 인접 리스트
    static boolean[] visited;           // 방문 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        arr = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {   // 인접 리스트 초기화
            arr[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            // 양방향 에지이므로 양쪽에 더하기
            arr[s].add(e);
            arr[e].add(s);
        }

        int count = 0;
        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                count++;
                dfs(i);
            }
        }

        System.out.println(count);
    }

    static void dfs(int v) {
        if (visited[v]) {
            return;
        }
        visited[v] = true; // 방문한 적이 없다면 true로

        for (int i : arr[v]) {
            if (!visited[i]) {    // 연결 노드 중 방문하지 않았던 노드만 탐색하기
                dfs(i);
            }
        }
    }
}

👉 성능