백준 - 연결요소의 개수[java]

문제 출처: 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) 같은 간선은 한 번만 주어진다.

출력

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

예제 입력

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

예제 출력

2

문제 풀이

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

class Main {

    static int count;

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

        int[] total = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int numOfPoints = total[0];
        int numOfLines = total[1];
        int[][] allPoints = new int[numOfPoints][numOfPoints];
        for (int i = 0; i < numOfLines; i++) {
            int[] coord = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            allPoints[coord[0] - 1][coord[1] - 1] = allPoints[coord[1] - 1][coord[0] - 1] = 1;
        }

        boolean[] visited = new boolean[numOfPoints];
        for (int i = 0; i < allPoints.length; i++) {
            if(!visited[i]) {
                count++;
                counting(allPoints, visited, i);

            }
        }
        System.out.println(count);
        br.close();
    }

    public static void counting(int[][] allpoints, boolean[] visited, int row) {

        visited[row] = true;
        for (int i = 0; i < allpoints.length; i++) {
            if (allpoints[row][i] == 1 && !visited[i])
                counting(allpoints, visited, i);
        }
    }
}

그래프의 연결 요소 란 아래 그림을 참고 하면 된다. 아래 그래프의 연결 요소는 총 2개이다.

풀이 방법

1. 일단 입력받은 좌표를 이차원 배열에 입력한다. ([1,5]가 들어오면 [5,1]도 같이 입력 해주어야함)

2. 총 그래프 좌표 수의 크기로 visited 배열을 만들고 DFS 알고리즘으로 시작 되는 좌표 부터 연결된 모든 좌표를 마킹한다.

3. 모든 좌표를 돌았을때 총 몇번 DFS를 call했는지가 연결요소의 개수가 된다.