백준) 11724 - 연결 요소의 개수 [Java]

문제)

 방향 없는 그래프가 주어졌을 때, 연결 요소 (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;
import java.util.ArrayList;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        int answer = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NM = br.readLine().split(" ");
        int N = Integer.parseInt(NM[0]);
        int M = Integer.parseInt(NM[1]);

        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();

        for (int i=1; i <= N; i++) {
            map.put(i, new ArrayList<>());
        }

        for (int i=0; i < M; i++) {
            String[] uv = br.readLine().split(" ");
            int u = Integer.parseInt(uv[0]);
            int v = Integer.parseInt(uv[1]);
            map.get(u).add(v);
            map.get(v).add(u);
        }

        int[] check_list = new int[N];

        for (int i=1; i <= N; i++) {
            if (check_list[i-1] == 0) {
                DFS(i, map, check_list);
                answer += 1;
            }
        }

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

    static void DFS(int node, HashMap<Integer, ArrayList<Integer>> map, int[] chk_lst) {
        for (Integer i : map.get(node)) {
            if (chk_lst[i-1] == 0) {
                chk_lst[i-1] = 1;
                DFS(i, map, chk_lst);
            }
        }
    }
}

풀이 :

프로그래머스) 네트워크 [Java]

 해당 문제의 풀이와 유사함.