[백준/자바] 1717 집합 표현하기
📌 문제
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
⚔ 입력
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.
📣 출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)
💎 문제분석하기
유니온 파인드 대표 문제라고 할 수 있다
문제에서 "합집합 연산"은 유니온 연산을 의미하고
"두 원소가 같은 집합에 포함돼 있는지를 확인하는 연산"은 파인드 연산을 의미한다
예제 입력에서 0 1 3 은 1번과 3번을 합치라는 뜻이며
1 1 7은 1번과 7번의 원소가 같은지를 확인한다는 뜻이다
i) 처음 각 노드의 대표로 자기 자신을 초기화 한다
배열 인덱스 1 2 3 4 5 6 7
원소 1 2 3 4 5 6 7
ii) 이후 문제의 요구사항에 따라 쿼리를 실행한다
e.g. 0 1 3 => union(1,3)
=> 1 2 3 4 5 6 7
1 2 1 4 5 6 7
=> 이 연산으로 1과 3이 한 집합이 되며 대표 노드인 1로 정해짐
e.g. 1 1 7 => find(1) == find(7) 확인
=> 1 2 3 4 5 6 7
1 2 1 4 5 6 7
=> 1번과 7번 자리의 원소가 다르므로 no를 반환
find의 로직은 다음과 같다
=> e.g. find(6)
=> 1 2 3 4 5 6
1 2 3 1 1 5
=> idx 값과 value 값 비교
=> A[6] vs 6 => 다름 => value인 5를 find의 var로 사용 => find(5)
=> A[5] VS 5 => 다름 => vlaue인 1을 find의 var로 사용 => find(1)
=> A[1] vs 1 = > 같음 => 대표 노드가 설정되면서 5, 6의 노드가 1로 설정됨
💡 코드 구현하기
import java.util.Scanner;
public class Main {
private static int[] representativeNode;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int nodes = scanner.nextInt();
int queries = scanner.nextInt();
representativeNode = new int[nodes + 1];
initialRepresentativeAsSelf(nodes);
for (int i = 0; i < queries; i++) {
int command = scanner.nextInt();
int nodeNumber1 = scanner.nextInt();
int nodeNumber2 = scanner.nextInt();
handleCommand(command, nodeNumber1, nodeNumber2);
}
}
private static void handleCommand(int command, int nodeNumber1, int nodeNumber2) {
if (command == Command.valueOf("union").getCommandType()) {
union(nodeNumber1, nodeNumber2);
} else {
if (isSameElement(nodeNumber1, nodeNumber2)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
// 자기 자신으로 처음 대표 요소를 치기화
private static void initialRepresentativeAsSelf(int nodes) {
for (int i = 0; i <= nodes; i++) {
representativeNode[i] = i;
}
}
// 대표 노드끼리 연결하는 유니온 연산
public static void union(int node1, int node2) {
node1 = find(node1); // 대표 노드를 먼저 찾기
node2 = find(node2);
if (node1 != node2) {
representativeNode[node2] = node1;
}
}
public static int find(int node) {
if (node == representativeNode[node]) // 해당 노드의 요소가 대표 노드면 리턴
return node;
else
return representativeNode[node] = find(representativeNode[node]); // 아니라면 해당 노드의 노드값을 이동하여 index와 value 값이 같을 때까지 확인
}
// 각 원소가 한 집합 안에 있는지 확인
private static boolean isSameElement(int node1, int node2) {
node1 = find(node1);
node2 = find(node2);
return node1 == node2;
}
private enum Command {
union("union", 0),
find("find", 1);
private final String commandName;
private final int commandType;
Command(String commandName, int commandType){
this.commandName = commandName;
this.commandType = commandType;
}
public int getCommandType() {
return commandType;
}
}
}
풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편
'알고리즘 > 백준' 카테고리의 다른 글
[백준/자바] 11404 플로이드 (0) | 2022.11.26 |
---|---|
[백준/자바] 1948 임계경로 (0) | 2022.11.26 |
[백준/자바] K번째 수 (0) | 2022.11.24 |
[백준/자바] 1167 트리의 지름 (0) | 2022.11.23 |
[백준/자바] 13023 ABCDE 친구 관계 파악하기 (0) | 2022.11.23 |