[SWEA] 창용 마을 무리의 개수

창용 마을에는 N명의 사람이 살고 있다.

사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.

두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다.

두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면,

이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다.

문제

창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는

두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다.

이후 M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호가 주어진다.

같은 관계는 반복해서 주어지지 않는다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

무리의 개수를 출력한다.

풀이

DFS 로 푼 경우

import java.util.Scanner;
import java.io.FileInputStream;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Solution
{
    static boolean[] visited;
    static int cnt;
    // 그래프 입력을 위한 배열 선언
    static ArrayList<Integer>[] g;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tn = Integer.parseInt(br.readLine().trim());
 
        // 테스트 케이스 개수만큼 시행
        for (int tc = 1; tc <= tn; tc++) {
            cnt = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 마을에 사는 사람 수(정점 수)
            int M = Integer.parseInt(st.nextToken()); // 서로를 알고 있는 관계 수 (간선 수)
//            ArrayList<Integer[]> g = new ArrayList<>();
 
            g = new ArrayList[N+1];
            for(int i = 1; i <= N; i++){
                g[i] = new ArrayList<>();
            }
            // 간선 수만큼 그래프 정보 입력 받음
            for (int j = 0; j < M; j++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine());
                int f = Integer.parseInt(st2.nextToken());
                int s = Integer.parseInt(st2.nextToken());
                g[f].add(s);
                g[s].add(f);
            }
 
            // dfs 방문을 위한 방문 - 원소마다 돌면서 방문안했으면 방문
            visited = new boolean[N+1];
            cnt = 0;
            for (int s = 1; s <= N; s++) {
                if(visited[s] == false){
                    cnt += 1;
                    visited[s] = true;
                    dfs(s);
                }
            }
 
            System.out.print("#" + Integer.toString(tc) + " " + Integer.toString(cnt));
            System.out.println();
        }
 
    }
 
    static void dfs(int node){
        for(int nn: g[node]){
            if(visited[nn] == false){
                visited[nn] = true;
                dfs(nn);
            }
        }
    }
}

유니온 파인드로 푼 경우

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Solution
{
    static int T;
    static int[] count;
    static int[] parent;
 
    static void union(int n1, int n2){
        int k1 = find(n1);
        int k2 = find(n2);
 
        if(k1 < k2){
            parent[k2] = k1;
            count[k1] += count[k2];
            count[k2] = 0;
        }
        else if (k1 > k2){
            parent[k1] = k2;
            count[k2] += count[k1];
            count[k1] = 0;
        }
    }
 
    static int find(int n){
        // node 가 자신의 최상위 정점(부모)일때까지 돌림
        // 자신의 parent 가 자신일때까지
        int node = n;
        while(parent[node] != node){
            node = parent[node];
        }
        return node;
    }
 
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine().trim());
 
        for(int tc = 1; tc <= T; tc++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
 
            // 해당 원소를 정점으로 가지는 트리(그룹) 내 원소 수를 저장
            count = new int[N+1];
            Arrays.fill(count, 1);
            // 해당 원소가 트리 내 가장 상위 부모로 가지는 원소의 인덱스를 저장(기본값은 자신)
            parent = new int[N+1];
            for(int tmp = 1; tmp <= N; tmp++) parent[tmp] = tmp;
            // 간선정보를 토대로 서로소 그룹화 진행
            for (int i = 1; i <= M; i++) {
                st = new StringTokenizer(br.readLine());
                int f = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());
 
                union(f, s);
            }
            // 무리 개수 세기
            int ans = 0;
            for(int i = 1; i < count.length; i++){
                if(count[i] != 0) ans += 1;
            }
            System.out.print("#" + tc + " " + ans);
            System.out.println();
        }
 
    }
 
}