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

       문제 요약        

- 문제

- 1 ~ N 번까지 사람까지 번호

- 알 수 있는 관계라면, 하나의 무리라고 함

- 몇 개의 무리가 존재하는지 계산하는 프로그램

 

- 입출력

 

         아이디어        

- 아이디어1 : 연결 관계가 주어지므로, 해당 관계를 끝까지 탐색해서 관계들의 집합을 알아낸다. [DFS]
- 아이디어2 : 관계들의 집합 [Disjoint Set]

 

 

         소스코드        

1. DFS

package _week04._0227.ws;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class S7465_dfs {
    static int T;
    static int N, M;
    static List<Integer>[] phones;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine()); // 테스트 케이스의 수

        StringTokenizer st;
        for (int test = 1; test <= T; test++) { // 공백 하나로 구분되어 주어짐
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 사람의 수 vertex
            M = Integer.parseInt(st.nextToken()); // 관계의 수 edge
            phones = new List[N+1];
            for (int n = 0; n <= N; n++) {
                phones[n] = new ArrayList<>();
            }
            for (int m = 0; m < M; m++) {
                st = new StringTokenizer(br.readLine());
                int a= Integer.parseInt(st.nextToken())-1;
                int b = Integer.parseInt(st.nextToken())-1;
                phones[a].add(b);
                phones[b].add(a);
            }
            int cnt =0;
            visited = new boolean[N+1];
            for (int i = 0; i < N; i++) {
                if (!visited[i]) { // 나머지 친구의 친구관계 확인
                    cnt++;
                    dfs(i); //i의 모든 친구 관계 결정됨
                }
            }
            System.out.println("#"+test+" "+cnt);
        }
    }

    private static void dfs(int now) {
        visited[now] = true;
        for (int next : phones[now]) {
            if(visited[next])continue;
            dfs(next);
        }
    }
}

2. Disjoint Set

package _week04._0227.ws;

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

public class S7465_disjointSet {
    static int T;
    static int N, M;
    static int[] parent;
    static boolean[] visited;
    static int[] depth;

    public static void main(String[] args) throws IOException {
        // 1 ~ n개의 집합을 이루고 있음
        // 합집합 연산, 두 원소가 같은 집합에 포함되어 있는지 연산 수행
        //System.setIn(new FileInputStream("src/_week04/ws/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine()); // 테스트 케이스의 수

        StringTokenizer st;
        for (int test = 1; test <= T; test++) { // 공백 하나로 구분되어 주어짐
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 사람의 수 vertex
            M = Integer.parseInt(st.nextToken()); // 관계의 수 edge

            parent = new int[N + 1]; //1 ~ N 번 사람번호
            for (int i = 1; i <= N; i++) {
                parent[i] = i;
            }

            visited = new boolean[N + 1];
            depth = new int[N + 1];
            for (int m = 0; m < M; m++) { // M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호
                st = new StringTokenizer(br.readLine()); // "인접"하다
                union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }
            Set<Integer> set  = new HashSet<>();
            for(int i=1;i<=N;i++){
                set.add(find(parent[i]));
            }


            System.out.println("#" + test + " "+set.size());
        }
    }

    private static void union(int a, int b) {
        int aParent = find(a);
        int bParent = find(b);
        if (depth[aParent] < depth[bParent]) {
            parent[aParent] = bParent;
        } else {
            parent[bParent] = aParent;
        }
        if (depth[aParent] == depth[bParent]) {
            depth[aParent]++;
        }
    }

    private static int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }

}