[백준 알고리즘] 11724번 : 연결 요소의 개수

문제

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

입력

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

출력

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

코드

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

public class BOJ_11724 {
    static int vertex, edge;
    static int[][] graph;
    static boolean[] visited;

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

        String[] str1 = br.readLine().split(" ");
        vertex = Integer.parseInt(str1[0]);                     //정점의 개수
        edge = Integer.parseInt(str1[1]);                       //간선의 개수

        graph = new int[vertex + 1][vertex + 1];

        for (int i = 0; i < edge; i++) {
            String[] str2 = br.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);

            // 방향성을 주기 위해서 [a][b]와 [b][a] 모두 1 저장
            graph[a][b] = graph[b][a] = 1;
        }

        visited = new boolean[vertex + 1];

        int count = 0;
        for (int i = 1; i <= vertex; i++) {
            if (!visited[i]) {
                dfs(i);
                ++count;
            }
        }
        System.out.println(count);
    }

    public static void dfs(int start) {
        visited[start] = true;

        for (int i = 1; i <= vertex; i++) {
            if (graph[start][i] == 1 && !visited[i]) dfs(i);
        }
    }
}

풀이 및 느낀점

연결된 정점을 2차원 그래프 배열에 저장했다. 만약 (2, 3)을 입력 받았다면 graph[2][3]과 graph[3][2]에 모두 1을 저장했다. 방향성을 주기 위함이었다. visited 배열을 생성하였고, dfs 메소드 내에서 visited 배열을 이용하여 방문여부를 확인하면서, 방향성을 준 graph 배열에 접근했다.

참고자료