https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU
https://todaycode.tistory.com/108
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();//스트림을 닫음
'Algorithm > swea' 카테고리의 다른 글
swea 3124 최소 스패닝 트리 //Kruskal 알고리즘 (0) | 2022.08.24 |
---|---|
swea 3289 서로소 집합 (0) | 2022.08.24 |
1247. [S/W 문제해결 응용] 3일차 - 최적 경로 (0) | 2022.08.19 |
3234. 준환이의 양팔저울 (0) | 2022.08.19 |
5644. [모의 SW 역량테스트] 무선 충전 (0) | 2022.08.17 |