swea 7465 창용 마을 무리의 개수 //유니언 파인드, 버퍼드라이터

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU 

SW Expert Academy

https://todaycode.tistory.com/108

Union-Find 쉽게 이해하기

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

/**
 * 
 * @author
 * * 유니언 파인드 => 그룹판별
 * 루트같음->같은그룹
 * 루트다름->다른그룹
 * find => (최고조상)루트번호찾기
 * 루트갯수==그룹갯수
 * 
 * 
 */
public class Solution_7465_유동훈 {
	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];
			//root[index]==index의 부모가 누구냐?
 
			// 자기 자신을 가르키도록
			//처음에는 원소 각각  홀로 존재
			for (int i = 1; i <= N; i++) {
				root[i] = i;
			}
 
			// 두 사람의 번호를 union
			//(from을 to에 연결)
			//from의 루트를 to의 루트에 연결
			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();
	}
 
	/**
	 * 
	 * @param x : x의 루트(최고조상)를 찾아라
	 * @return : 루트노드 번호
	 */
	public static int find(int x) {
		//x의 부모== x->내가 루트임.
		if (root[x] == x) 
		{
			return x;
		}
		//아니면 내 부모의 부모를 찾아라
		//반복
		else 
		{
			return find(root[x]);
		}
	}
 
	/**
	 * 
	 * @param a
	 * @param b
	 * (A를 B에 연결)
	 * A의 루트노드를 B의 루트노드에 연결
	 * (A위에 B를 부모로)
	 */
	public static void union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
 
		if (rootA == rootB) return;
		
		//A의 루트노드를 B의 루트노드에 연결
		root[rootA] = rootB;
	}
}

 

* 버퍼드 라이터 => 출력많을때 성능개선

sysout 개선

sb.append("#").append(tc).append(" ").append(hs.size()).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();//남아있는 데이터를 모두 출력시킴
		bw.close();//스트림을 닫음