문제 분석

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

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

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

두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, -> 연결되어 있다면

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

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

이 문제는 DFS 탐색을 통해 연결되어있는지 확인하거나 혹은 유니온 파인드를 통해 무리가 몇개 있는지 확인하면 된다.

문제풀이

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

/**
 * @author 신온유
 * @git
 * @youtube
 * @performance
 * @category dfs & 유니온 파인드
 * @note
 * 창용 마을 무리의 개수
 * 무리의 개수를 구하는 것 -> dfs 탐색 or union find를 통한 방법 두가지 가능
 * dfs의 탐색횟수를 구하면 되고,유니온 파인드의 경우 같은 집합에 포함되어있는지 대표 노드를 찾으면 된다
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU#
 * @since 2023-09-15
 **/
public class Solution {
    static int T;
    static int N,M;
    static int[][] graph;
    static boolean[] visited;
    static int answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());

        for(int t = 0;t < T; t++){
            st = new StringTokenizer(br.readLine()," ");

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            graph = new int[N+1][N+1];
            visited = new boolean[N+1];
            answer = 0;

            for(int m = 0; m < M; m++){
                st = new StringTokenizer(br.readLine()," ");

                int i = Integer.parseInt(st.nextToken());
                int j =  Integer.parseInt(st.nextToken());

                graph[i][j] = 1;
                graph[j][i] = 1;
            }

            for(int i=1;i<=N;i++){
                if(!visited[i]) answer += dfs(i);
                // visited 배열을 확인하며, 방문하지 않은 사람노드로 들어간다
                // 한 사람과 연결된 사람을 모두 찾아낸다, 즉 dfs 를 빠져나온 횟수만큼 무리의 개수가 있다
            }

            System.out.printf("#%d %d",t+1,answer);
            System.out.println();
        }
    }

    static int dfs(int start){
        visited[start] = true;
        for(int i=1;i<=N;i++){
            if(graph[start][i] == 1 && !visited[i]) dfs(i);
            // 방문하지 않았으면서, 1(연결되어있으면) 순회
        }
        return 1;
        //무사히 빠져나가면 return 1을 한다
    }
}

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

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * 유니온 파인드로 풀어보기
 * @see
 * @since 2023-10-11
 **/
public class Solution {
    static int T;
    static int N, M; // 노드의 수, 간선의 개수
    static int[] parent; // 부모노드를 저장 할 배열
    static int answer; // 정답을 저장할 변수

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

        T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine(), " ");

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            parent = new int[N+1]; // 1부터 저장할 것이기 때문에 하나 더 크게 저장해줍니다
            answer = 0;
            for(int i=1;i<=N;i++) parent[i] = i;

            for (int m = 0; m < M; m++) {
                st = new StringTokenizer(br.readLine(), " ");

                int i = Integer.parseInt(st.nextToken());
                int j = Integer.parseInt(st.nextToken());
                union(parent,i,j); // 변수를 입력 받을때마다 union 연산을 통하여 연결해줍니다
            }

            for(int i=1;i<=N;i++){
                if(parent[i] == i) answer++;
            }
            //자기자신을 가리키는 노드의 개수 = 무리의 개수 
            //자기자신을 가리키는 노드가 대표 부모이기 때문이다.

            System.out.printf("#%d %d \n",t+1,answer);
        }
    }

    // union find
    // union method
    static void union(int[] parent,int x,int y){
        // a와 b를 합쳐준다
        // 부모를 같게 만들어준다
        // 부모를 끝까지 찾아내서 부모를 같게 해주기
        x = find(parent,x);
        y = find(parent,y);

        if(x < y) parent[y] = parent[x];
        else parent[x] = parent[y];
    }
    // find method
    static int find(int[] parent,int x){
        // 부모 인자를 찾아준다
        if(x == parent[x]) return x; // 자기자신을 부모로 가지고 있는 노드 일 경우
        //자기 자신을 리턴한다
        else return parent[x] = find(parent,parent[x]);

    }
}