[실버 2] [Java] 백준 11724번: 연결 요소의 개수

아이디어

graph에서 연결 요소(Connected Component)란, 연결되어있는 군집의 개수와 같다

예를 들면 그래프가

1-2-3 4-5 6-7-8 9

위와 같이 구성되어 있다면, 연결 요소는 (1-2-3), (4-5), (6-7-8), (9)의 4개이다.

 

일반적인 bfs나 dfs는 하나의 연결 요소에 대해서만 탐색할 수 있으므로

boolean[] visited가 모두 true가 되기 전까지 반복하여 탐색을 진행하면 연결 요소의 개수를 구할 수 있다.

 

bfs나 dfs를 이용해서 우선 하나의 노드에 대해 인접 노드를 탐색하고, 탐색을 할 때마다 연결 요소의 개수를 1개씩 추가한다.

 

그렇게 하나의 연결 요소 탐색이 끝나면 visited가 false인 노드에 대해 다시 탐색을 시작하고, 이를 반복한다.

 

이를 코드로 구현하면 다음과 같다.

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class N11724 {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static int components = 0;

    public static void dfs(int V) {
        visited[V] = true;

        for (Integer i : graph.get(V)) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

    public static void bfs(int V) {
        Queue<Integer> q = new LinkedList<>();
        q.add(V);
        visited[V] = true;

        while (!q.isEmpty()) {
            int node = q.poll();
            for (int i : graph.get(node)) {
                if (!visited[i]) {
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int N =  Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        visited = new boolean[N+1];

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 1; i <= M; i++) {
            input = br.readLine().split(" ");
            int node = Integer.parseInt(input[0]);
            int neighbor = Integer.parseInt(input[1]);
            graph.get(node).add(neighbor);
            graph.get(neighbor).add(node);
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                components++;
                bfs(i);
            }
        }

        bw.write(components+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.