
https://www.acmicpc.net/problem/1717
문제분석
대충 보면 쉬운 문제다. 물론 그렇게 보이는대로 풀면(나)....바로 시간초과가 난다.
첫 풀이는, Union별로 ArrayList를 관리하면서 직접 합치며 풀려고 했다. 이렇게 하니, 메모리 초과로 인해 문제를 틀렸다(이제보니 메모리도 다른 문제와는 좀 다르게, 128MB만 준다).
따라서 다른 풀이로 접근해야 한다. 우리가 원하는건 해당 원소가"어느 집합" 에 속해있는지 이지, 해당 집합에 "어떤 원소들" 이 존재하는지가 아니다. 따라서 부모-자식 관계를 통해 마치 트리처럼 집합 소속 여부를 확인하게 할 수 있다.

이러한 원리로 소속을 저장한다. 중요한 점은, 부모의 경우는 parent[idx] = idx이고, 병합할때는 병합 기준의 parent 를 꼭 저장해야 한다.
코드
import java.util.*;
import java.io.*;
public class Main {
public static int[] parent;// 인덱스 n의 부모는 누구인지 저장. 부모가 같으면 같은 union
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
parent = new int[N+1]; // 0부터 n까지
for(int i = 0; i < N + 1; i++){// 0부터 N까지 넣어야 함
parent[i] = i;
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int direct = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(direct == 0){ // a 집합에 b 집합 편입
union(a,b);
}else if(direct == 1){// a와 b가 같은 집합인지(같은 부모인지)
bw.write(findParent(a) == findParent(b)? "YES" : "NO");
bw.newLine();
}
}
bw.flush();
bw.close();
}
public static int findParent(int n){
if(n == parent[n]){
return n;
}else{
return findParent(parent[n]);
}
}
// a집합으로 b집합 편입
public static void union(int a, int b){
// b의 parent의 parent를 a의 parent로 초기화(같은 집합)
int aParent = findParent(a);
int bParent = findParent(b);
parent[bParent] = aParent;
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 1918 후위 표기식 (0) | 2026.02.20 |
|---|---|
| [JAVA] 백준 7576 토마토 (0) | 2026.02.19 |
| [JAVA] 백준 3190 뱀 (0) | 2026.02.17 |
| [JAVA] 백준 17298 오큰수 (0) | 2026.02.16 |
| [JAVA] 백준 1987 알파벳 (0) | 2026.02.16 |