연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

문제 풀이

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

public class Main {
    static boolean[] visited;
    static int N,M;
    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());
        M=Integer.parseInt(st.nextToken());

        int[][] map=new int[N][N];
        visited=new boolean[N];
        int count=0;

        for(int i=0;i<M;i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());

            map[a-1][b-1]=1;
            map[b-1][a-1]=1;
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(map[i][j]==1 && !visited[j]){
                    visited[j]=true;
                    dfs(map,j);

                    count++;
                }
            }
        }

        for(int i=0;i<N;i++){
            if(!visited[i]) count++;
        }

        System.out.print(count);
    }

    private static void dfs(int[][] map, int j) {
        for(int a=0;a<N;a++){
            if(!visited[a] && map[j][a]==1){
                visited[a]=true;
                dfs(map,a);
            }
        }
    }
}

DFS 탐색이 몇 번 일어나는지 계산하면 연결되어있는 노드의 개수를 구할 수 있는 문제였다.

여기서 주의해야할 점은 무방향 그래프이기 때문에 간선을 표시할 때 양쪽 모두 표시해주어야한다.

main

for(int i=0;i<M;i++){
    st=new StringTokenizer(br.readLine());
    int a=Integer.parseInt(st.nextToken());
    int b=Integer.parseInt(st.nextToken());
    
    map[a-1][b-1]=1;
    map[b-1][a-1]=1;
}

for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
        if(map[i][j]==1 && !visited[j]){
            visited[j]=true;
            dfs(map,j);
            
            count++;
        }
    }
}

무방향 그래프이기 때문에 map[a-1][b-1]=1 뿐만 아니라 map[b-1][a-1]=1 도 해주어야한다.

map[i][j]이 연결되어있다는 것이 확인되고 j번째 노드가 방문되지 않았다면 dfs 탐색에 j노드를 매개변수로 보내주어 탐색해보고 탐색이 끝나면 count를 증가해준다.

DFS 탐색

private static void dfs(int[][] map, int j) {
    for(int a=0;a<N;a++){
        if(!visited[a] && map[j][a]==1){
            visited[a]=true;
            dfs(map,a);
        }
    }
}

j번째 노드를 매개변수로 받았기 때문에 j행을 살펴보고 연결되어있는 간선을 찾으면 된다.

연결되어있는 간선을 찾았고 해당 노드가 방문하지 않았음을 확인하면 방문표시를 해준뒤 해당 노드를 연결한 간선들에 대해 DFS 탐색을 다시 수행한다.

이렇게 DFS 탐색을 모두 반복하고 나면 연결되어있는 노드들에 대해 연결 요소의 개수를 구할 수 있다.

하지만 아무 노드와도 연결되어있지 않은 노드의 개수를 빼고 계산한 것이기 때문에 독립적으로 나와있는 노드의 개수도 구하여 값을 더해준다.

for(int i=0;i<N;i++){
    if(!visited[i]) count++;
}

이 과정까지 마치면 정답을 출력할 수 있다.