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

📌 문제

7465. 창용 마을 무리의 개수

📌 문제 해석

창용 마을에 N명의 사람이 살고 있으며, 1번 부터 N번 까지 사람의 번호가 붙어있다고 가정한다.
두 사람은 서로 아는 관계일 수도 아닐 수도 있는데,
만약 두 사람이 서로 아는 관계이거나, 아는 사람들을 거쳐서 알 수 있는 관계라면 하나의 무리로 칭한다.

창용 마을에는 몇 개의 무리가 존재하는지 계산하는 문제이다.

📌 설계

이 문제는 DFS 로도 풀 수 있고, 유니온 파인드를 통해서 풀 수도 있는 문제이다.
나 같은 경우는 DFS보다 유니온 파인드 접근이 먼저 생각 났고,
해당 문제를 유니온 파인드로 접근하여 문제를 해결했다.

✍ 입력

2    // 테스트 케이스 개수
6 5  // 첫 번째 테스트 케이스, N = 6, M = 5
1 2
2 5
5 1
3 4
4 6

위와 같이 N의 사람의 명수와 M개의 서로 아는 사람의 관계의 수를 나타낸다.
유니온 파인드 기본 연산을 알고 있었기 때문에
관계의 수를 받을 때마다, Union 연산을 해주었다.

그리고 M번의 유니온 연산이 끝나면,
마지막에 대표자들을 Set 자료구조에 담아
몇명의 대표가 남아있는지 확인하여 결과를 출력했다.

이 문제는 처음에 연결리스트를 활용해서 풀었는데, 단순히 부모 배열을 1차원으로 만들어서 풀어내도 될 것 같다.

📌 코드

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

public class Test_7465 {
	static class LinkNode {
		int data ; 
		LinkNode next;
		LinkNode parents;
		
		
		public LinkNode(int data) {
			super();
			this.data = data;
			this.parents = this;
		}
	}
	
	static int TC;
	static int N, M;
	static LinkNode[] list ;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens;
		StringBuilder sb = new StringBuilder();
		TC = Integer.parseInt(br.readLine());
		for(int t = 1; t <= TC; t++) {
			tokens = new StringTokenizer(br.readLine());
			N = Integer.parseInt(tokens.nextToken());
			M = Integer.parseInt(tokens.nextToken());
			
			list = new LinkNode[N+1];
			for(int i = 1; i <= N; i++) {
				list[i] = new LinkNode(i);
			}
			
			
			for(int m = 0; m < M; m++) {
				tokens = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(tokens.nextToken());
				int y = Integer.parseInt(tokens.nextToken());
				union(list[x],list[y]);
			}	
			Set<Integer> result = new HashSet<>();
			
			for(LinkNode tmp : list) {
				if(tmp == null) continue;
				result.add(findSet(tmp).data);
			}
			sb.append("#"+ t).append(" ").append(result.size()).append("\n");
		}
		System.out.println(sb);
	}

	private static void union(LinkNode x, LinkNode y) {
		LinkNode px = findSet(x);
		LinkNode py = findSet(y);
		
		if(px == py) return;
		
		LinkNode current = py;
		if(current != null) {
			current.parents = px;
		}
		
	}
	
	private static LinkNode findSet(LinkNode x) {
		
		if(x != x.parents) {
			x.parents = findSet(x.parents);
		}
		
		return x.parents;
	}
	
	

}

📌 메모리 / 시간

26,212 kb 메모리
129 ms 시간