swea 7465 창용 마을 무리의 개수 Java (dfs, union-find)

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU 

SW Expert Academy

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

창용 마을에는 N명의 사람이 살고 있다.
사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.
두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다.
두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면,
이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다.
창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는
두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다.
이후 M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호가 주어진다.
같은 관계는 반복해서 주어지지 않는다.

[출력]

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

풀이

swea를 많이 풀어보진 않았지만, swea치고는 지문이 굉장히 짧은 문제였다.

짧은 만큼 기본적인 개념을 공부할 수 있는 좋은 문제였다.

 

dfs/bfs 혹은 유니온 파인드로 풀 수 있는 문제이다.

문제에서 대놓고 노드들을 그룹핑하라고 했기 때문에 유니온 파인드가 좀 더 적절하지 않을까

무튼 본인은 dfs와 유니온 파인드 두 방식으로 풀었다.

 

dfs 풀이부터 설명하자면 주어진 간선을 양방향 간선으로 저장하고,

1번부터 n번 노드 모두 dfs를 돌리는데, 1번 노드부터 dfs를 시작해서 visited check를 이용해 그룹을 만들어 나간다.

이후 2번 노드가 visited된 상태라면 이미 그룹핑이 된 노드이기 때문에 스킵하고 다음 노드에 dfs를 돌린다.

이런 식으로 n번까지 탐색하면서 만들어지는 그룹의 개수를 세면 끝! 간단하다.

 

유니온 파인드 풀이도 간단하다.

https://www.secmem.org/blog/2021/03/21/Disjoint-Set-Union-find/

disjoint set이란 개념이 있는데 이건 딱히 몰라도 유니온 파인드를 공부하면 알게 되는 내용이라 disjoint set이 뭐다!

라고 딱 알고 있을 필요까진 없을 것 같다. 당연히 알고 있으면 더 좋다.

무튼 parent배열을 두고 안의 요소는 각자 자기를 향한다. 초기의 형태는 다음과 같다.

idx	1	2	3	4	5	6
val	1	2	3	4	5	6

이 parent배열에서 간선을 조회해서 만약 간선이 1,3이라면 값이 더 낮은 1로 그룹핑한다.

idx	1	2	3	4	5	6
val	1	2	1	4	5	6

이런 식으로 주어진 간선으로 그룹핑 가능한 모든 노드를 연결하면 2번 테스트케이스의 결과는 다음과 같다.

idx	1	2	3	4	5	6
val	1	1	1	1	1	3

이 배열을 해석하면, 1,2,3,4,5,6 모두 한 그룹이란 걸 알 수 있다.

하지만 이 상태로 정답을 추출하기엔 무리가 있다. 6도 1,2,3,4,5와 같은 그룹이지만 현재 3이란 값이 들어있기 때문이다.

이 배열의 또 다른 의미는 인덱스와 엘리먼트 값이 같은 것의 개수가 그룹의 개수이다.

그룹핑하는 과정에서 우리는 값이 작은 쪽으로 그룹명을 몰아줬기 때문이다.

 

이전 유니온 파인드 관련 문제에서 자세히 설명한 적이 있었...나? 있었을 것이기 때문에 알고리즘에 관한 설명은 러프하게 했다.

 

코드1(dfs)

import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Solution {

	static int n,m;
	static int[] input;
	static boolean[] visited;
	static ArrayList<Integer>[] edge;
	
	static void dfs(int cur) {
		visited[cur] = true;
		
		for(int next : edge[cur]) {
			if(visited[next]) continue;
			dfs(next);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			//input
			int answer=0;
			StringTokenizer tk = new StringTokenizer(br.readLine());
			n = Integer.parseInt(tk.nextToken());
			m = Integer.parseInt(tk.nextToken());
			input = new int[n+1]; 
			visited = new boolean[n+1];
			edge = new ArrayList[n+1];
			for(int i=1; i<= n; i++) {
				edge[i] = new ArrayList<Integer>();
			}
			for(int i=0; i<m; i++) {
				int from,to;
				tk = new StringTokenizer(br.readLine());
				from = Integer.parseInt(tk.nextToken());
				to = Integer.parseInt(tk.nextToken());
				edge[from].add(to);
				edge[to].add(from);
			}
			
			//solve
			for(int i=1; i<=n; i++) {
				if(visited[i]) continue;
				dfs(i);
				answer++;
			}
			
			//output
			bw.write("#" + t+ " " + answer +'\n');
		}
		bw.close();	
	}
}

코드1(union-find)

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

class Solution {
	 
    static int n,m;
    static int[] parent;

    static int getParent(int x) {
    	if (parent[x]==x) return x;
    	else return parent[x] = getParent(parent[x]);
    }
    
    static void unionParent(int x, int y) {
      x = getParent(x);
      y = getParent(y);
      
      if(x<y) 
    	  parent[y]=x;
      else 
    	  parent[x]=y;
    }
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
     
        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            //input
            int answer=0;
            StringTokenizer tk = new StringTokenizer(br.readLine());
            n = Integer.parseInt(tk.nextToken());
            m = Integer.parseInt(tk.nextToken());
            parent = new int[n+1];
            for(int i=1; i<=n; i++) {
            	parent[i] = i;
            }
            
          //solve
            for(int i=0; i<m; i++) {    
                tk = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(tk.nextToken());
                int to = Integer.parseInt(tk.nextToken());
                unionParent(from,to);
            }
             
            //부모 값이 자기 자신과 같은 것의 개수가 그룹의 개수
            for(int i=1; i<=n;i++) {
            	if(parent[i]==i) {
            		answer++;
            	}
            }
             
            //output
            bw.write("#" + t+ " " + answer +'\n');
        }
        bw.close(); 
    }
}