[백준 | Java] 11724 연결 요소의 개수

내 풀이

이 문제는 그래프의 연결 요소를 찾는 문제이므로 BFS로 풀었다.
(DFS로도 풀기 가능)

💡 연결 요소(Connected Component)

• 그래프에서 어떤 정점으로부터 다른 정점으로 갈 수 있는 경로들의 집합
• 연결 요소들은 그래프의 최대로 연결된 부분 그래프가 됨
  

그래프에 대한 더 많은 설명을 보고싶다면
👉 그래프와 그래프 구현 방법 포스팅

BFS에 대한 더 많은 설명을 보고싶다면
👉 BFS 포스팅

구현 아이디어는 다음과 같다.

1. 인접 행렬로 그래프 구현
2. 노드의 개수만큼 반복문 돌며,
   방문 체크를 하지 않은 노드를 만나면 그 노드는 BFS 수행
3. BFS 수행 횟수 카운팅 및 반환

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[][] graph;
    static boolean[] visited;
    static int N;

    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());  // 노드
        int M = Integer.parseInt(st.nextToken());  // 간선

        graph = new int[N + 1][N + 1];
        visited = new boolean[graph.length];

        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;
        }

        int cnt = 0;
        // 노드 0은 없으므로 1부터 시작해서 N까지 확인
        for (int i = 1; i <= N; i++) {
            if (visited[i] == true) {
                continue;
            }
            // 방문하지 않은 노드는 bfs 수행
            bfs(i);
            cnt++;
        }
        System.out.println(cnt);
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            start = queue.poll();

            for (int i = 0; i <= N; i++) {
                if (graph[start][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}