[Java] BOJ 11724 연결 요소의 개수

문제 

문제 링크 https://www.acmicpc.net/problem/11724

• 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
• 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
• 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
• 첫째 줄에 연결 요소의 개수를 출력한다.

아이디어

• 노드를 입력받을때마다 ArrayList로 서로 노드를 연결한다.
• for문을 사용하여 1부터 N까지의 노드를 돌면서 방문하지 않은 노드면 해당 노드로 BFS를 돌린다.
• 그리고 BFS를 이용하여 입력들어온 노드를 기준으로 연결된 노드를 방문하여 방문처리를 한다.
• 그래서 BFS를 돌릴때마다 카운트를 하나씩 더 해준다.

겪은 시행착오

• X

BFS를 사용하는 문제에 좀 익숙해진 것 같아서 좋았다!!

코드

import java.io.*;
import java.util.*;

public class BOJ11724 {

    static int N;
    static int M;
    static boolean visited[];
    static ArrayList<Integer> graph[];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 정점의 개수
        N = Integer.parseInt(st.nextToken());
        // 간선의 개수
        M = Integer.parseInt(st.nextToken());

        // 노드의 방문여부
        visited = new boolean[N + 1];

        // 연결된 정점을 저장할 ArrayList
        graph = new ArrayList[N + 1];

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

        for(int i = 0; i < M; i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine());

            // 기준 노드
            int a = Integer.parseInt(st2.nextToken());
            // 연결 노드
            int b = Integer.parseInt(st2.nextToken());

            // 서로 노드에 연결
            graph[a].add(b);
            graph[b].add(a);
        }

        // 연결 개수를 셀 변수
        int cnt = 0;

        // 노드 번호대로 돌다가
        for(int i = 1; i <= N; i++){
            // 방문하지 않은 노드가 있다면
            if(!visited[i]){
                // BFS를 돌리고
                BFS(i);

                // 연결 개수 + 1
                cnt = cnt + 1;
            }
        }

        System.out.println(cnt);
    }

    public static void BFS(int n){
        // 노드를 저장할 Queue
        LinkedList<Integer> q = new LinkedList<>();

        // Queue에 입력받은 값을 넣음
        q.offer(n);

        // 해당 노드 방문 처리
        visited[n] = true;

        while(!q.isEmpty()){
            // 맨 위의 끝 값을 따로 저장
            int node = q.peek();

            q.poll();

            // 노드랑 연결된 노드 수만큼 반복
            for(int i : graph[node]){
                // 해당 노드를 방문하지 않았다면
                if(!visited[i]){
                    // Queue에 해당 노드를 추가하고
                    q.add(i);

                    // 방문 처리
                    visited[i] = true;
                }
            }
        }
    }
}