7465번 - 창용 마을 무리의 개수

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

사람들과 사람들의 관계가 주어질 때 몇 개의 그룹이 존재하는 지를 출력하는 문제다.

푸는 방법은 DFS나 Union-Find를 사용하는 방법이 있을 듯하다.

우선 그전에 이 문제에서 주의해야 할 점이 있다.

 

 

입력 예시

 

예를 들어 위와 같은 입력이 들어왔다 치자.

위 예시에서 그룹은 총 몇 개일까? 2개? 땡!!!

혼자 있는 사람도 하나의 그룹으로 쳐서 세어줘야 한다.

 

이 문제에서는 혼자 있는 사람을 입력으로 주지 않고

주어지는 테스트 케이스에도 그런 경우가 없기 때문에 이 부분을 놓치기 쉽다.

하지만 히든 케이스에서 이 경우가 나오기 때문에 고려하지 않으면 실패가 뜬다.

 

특히 DFS로 문제를 풀 때 이 경우를 잘 생각하면서 코드를 짜야하고

Union-Find 개념을 사용하면 애초에 혼자 있는 노드도 하나의 집합이라는 개념이 들어있어서 문제없이 풀 수 있었던 문제인 것 같다.

 

 

Union-Find 알고리즘에 대해서는 여기에서 다루었다.

 

 

2. 코드

public class Solution {
	static int[] root;
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int testCase = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= testCase; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			root = new int[N + 1];

			// 자기 자신을 가르키도록
			for (int i = 1; i <= N; i++) {
				root[i] = i;
			}

			// 두 사람의 번호를 union
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());

				union(from, to);
			}
			
			// 루트 노드의 개수를 세기위함
			HashSet<Integer> hs = new HashSet<>();
			for (int i = 1; i <= N; i++) {
				hs.add(find(i));
			}

			sb.append("#").append(tc).append(" ").append(hs.size()).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	public static int find(int x) {
		if (root[x] == x) {
			return x;
		} else {
			return find(root[x]);
		}
	}

	public static void union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);

		if (rootA == rootB) return;
		root[rootA] = rootB;
	}
}

 

 

3. 실행시간

 

 

 

 

---

💡 느낀 점

• union 하는 부분에서 실수를 해서 2시간을 날려먹었다. 절대 안 잊어먹을 듯...
• Union-Find를 연습하기 좋은 문제인 것 같다. DFS로 풀다가 혼자인 사람도 그룹이라는 걸 알고 문제 진짜 별로고 치사하다고 생각했는데 Union-Find에 대해 공부하고 나서 좋은 문제라는 걸 알게 됐음.

---