링크

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

출력

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

풀이

import java.util.*;

public class boj_11724 {

    static ArrayList<Integer>[] arrayLists;
    static boolean visited[];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M =  scanner.nextInt();

        arrayLists = new ArrayList[N+1];
        visited = new boolean[N+1];

        int vertex1, vertex2, answer = 0;

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

        for (int i = 0; i < M; i++) {
            vertex1 = scanner.nextInt();
            vertex2 = scanner.nextInt();

            arrayLists[vertex1].add(vertex2);
            arrayLists[vertex2].add(vertex1);
        }

        for (int i = 1; i < N+1; i++) {
            if (!visited[i]) {
                dfs(i);
                answer++;
            }
        }

        System.out.println(answer);

    }

    static void dfs(int v) {
        if(visited[v])
            return;

        visited[v] = true;
        for (int i : arrayLists[v]){
            if(!visited[i]) {
                dfs(i);
            }
        }
    }
}

설명

문제에서 우선 '연결 요소'라는 것 자체가 좀 낯설었다. 간선으로 서로 연결된 노드들의 그룹을 연결 요소 하나로 보는 것 같아 찾아보니 내가 생각한 것이 맞았다. 아직 노드와 간선을 연결하고 탐색하는 것이 익숙치 않아 참고 링크를 걸어둔 블로그 글을 참고하여 이해해였다.

풀이 참고

https://hees-dev.tistory.com/46