[백준] 11724 : 연결 요소의 개수 - java [자바]

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

11724번: 연결 요소의 개수

이해

문제 풀이에 앞서 문제를 이해해보자.

• 연결 요소(Connected Component)는 연결된 정점의 집합을 의미한다. 다음 이미지에서의 연결 요소는 4개이다.
• 따라서 해당 문제는 그래프 탐색을 통해 연결된 정점을 모두 방문처리하고
• 방문처리 되지 않은 정점이 발견되면 새로운 연결 요소임을 의미한다.

https://www.mathworks.com/matlabcentral/fileexchange/46457-splitting-a-network-into-connected-components

풀이

• 전체 노드(1~N)를 순회하며 해당 노드가 방문되지 않았다면, 연결 요소(result)를 카운트한다.
• 해당 노드를 시작으로 그래프 탐색(BFS or DFS)을 진행하며 방문처리한다.(이 글에선 BFS를 구현했다)
• 주의* 연결된 노드를 발견과 동시에 방문처리하지 않으면 무한루프에 빠질 수 있으니 주의하자.

코드

package BOJ;

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

public class 연결_요소의_개수_11724 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        final int N = Integer.parseInt(input[0]);
        final int M = Integer.parseInt(input[1]);
        boolean[] visited = new boolean[N + 1];
        int result = 0;

        List<List<Integer>> graph = new ArrayList<>();

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

        for (int i = 0; i < M; i++) {
            String[] connectInfo = br.readLine().split(" ");
            int u = Integer.parseInt(connectInfo[0]);
            int v = Integer.parseInt(connectInfo[1]);

            graph.get(u).add(v);
            graph.get(v).add(u);
        }


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

            result += 1;

            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);

            while (!queue.isEmpty()) {
                Integer current = queue.poll();
                visited[current] = true;

                for (Integer node : graph.get(current)) {
                    if (!visited[node]) {
                        visited[node] = true;
                        queue.add(node);
                    }
                }
            }
        }


        bw.write(Integer.toString(result));

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