[BaekJoon] #11724 연결요소의 개수

문제접근

연결 요소의 개수를 구하기 위해 DFS나 BFS를 구현하고, 함수 호출 횟수를 세어야 합니다.

그래프 탐색 문제에서는 시작 정점을 주어 탐색을 시작하는 경우가 많지만, 이 문제에서는 시작 정점이 주어지지 않았습니다. 이럴 때는 방문 배열를 순회하며 아직 방문하지 않은 노드를 찾아 그래프 탐색을 수행할 수 있습니다.

탐색을 한 번 수행하면 연결된 모든 요소를 방문 처리해주기 때문에, 방문배열에서 아직 방문하지 않은 노드는 연결되지 않은 다른 요소 중 하나라고 볼 수 있습니다.

함수호출의 횟수 = 연결요소의 수 이므로, 함수 호출 이전에 count 를 세어주면 됩니다.

code

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

public class Main{
    static LinkedList<Integer>[] adjList;
    static boolean visited[];
    static int count =0;
    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()); // 간선개수
        adjList = new LinkedList[N+1];
        visited = new boolean[N+1];

        for(int i=1; i<N+1 ; i++){
            adjList[i] = new LinkedList<Integer>();
        }
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            adjList[v1].add(v2);
            adjList[v2].add(v1);
        }
        for(int i=1; i<N+1; i++){
            Collections.sort(adjList[i]);
        }
       
        for(int i=1; i<N+1; i++){
            if(!visited[i]){
                count++;
                //DFS(i);
                BFS(i);
            }
        }
        System.out.println(count);
    }
    private static void DFS(int v){
        visited[v] = true;
        for(int t: adjList[v]){
            if(!visited[t]){
                DFS(t);
            }
        }
    }
    private static void BFS(int v){
        Queue<Integer> q = new LinkedList<Integer>();
        visited[v] = true;
        q.add(v);
        while(!q.isEmpty()){
            int now = q.poll();
            for(int t:adjList[now]){
                if(!visited[t]){
                    visited[t]=true;
                    q.add(t);
                }
            }

        }


    }
}