[백준 - java] 1043번 : 거짓말
문제
설명
union-find를 이용해 문제를 해결했다.
- parent 배열을 초기화 할 때 진실을 아는 사람은 parent[x] = x으로 초기화 하고 아닌 사람은 parent[x] = 0으로 초기화 한다.
- 파티 참석 인원을 저장하기 위해 ArrayList[] partyList로 변수를 선언하고 각 파티를 돌면서 파티 인원을 추가한다.
- 파티 인원이 2명 이상일 경우 같은 집합으로 합친다. -> partyUnion()
- 각 파티를 돌면서 거짓말을 할 수 있는지 확인한다. -> isLie()
주의할 점
- 원래 union-find 연산을 사용할 때 parent 배열을 자기 자신의 인덱스로 초기화 하는데 이번 문제에서는 0으로 초기화 되어있기 때문에 find 메소드에서 if문에 (parent[x] == 0) 조건을 추가해야 한다.
- union() 메소드에서 최상위 원소가 같지 않을 경우 union 해주는데 이때 조건을 하나 더 추가해야 한다.
-> if (x == parent[x]) 조건(파티에 진실을 아는 사람이 있는 경우)을 추가해서 진실을 모르는 사람의 부모를 진실을 아는 사람이 되게 해준다. -> parent[y] = x
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer>[] partyList;
static int[] parent;
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());
partyList = new ArrayList[M];
parent = new int[N + 1];
st = new StringTokenizer(br.readLine());
int knowN = Integer.parseInt(st.nextToken());
for (int i = 0; i < knowN; i++) {
// 진실을 알고 있는 사람은 parent[num]에 num을 저장, 진실을 모르는 사람은 0
int num = Integer.parseInt(st.nextToken());
parent[num] = num;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int partyN = Integer.parseInt(st.nextToken());
partyList[i] = new ArrayList<>();
for (int j = 0; j < partyN; j++) {
partyList[i].add(Integer.parseInt(st.nextToken()));
}
// 파티에 참석하는 사람이 2명 이상일 경우 같은 집합으로 합침
if (partyList[i].size() >= 2) {
partyUnion(i);
}
}
int result = 0;
// 각 파티를 돌면서 거짓말 할 수 있는지 확인
for (int i = 0; i < M; i++) {
if (isLie(i)) {
result++;
}
}
System.out.println(result);
}
// 파티에 참석한 인원을 같은 집합으로 합침 : 맨 처음 값과 나머지 값들을 union하면 같은 집합이 됨
public static void partyUnion(int n) {
int first = partyList[n].get(0);
for (int i = 1; i < partyList[n].size(); i++) {
union(first, partyList[n].get(i));
}
}
// 파티에서 거짓말 할 수 있는지 확인
public static boolean isLie(int n) {
for (int i = 0; i < partyList[n].size(); i++) {
int num = find(partyList[n].get(i)); // 파티에 참석한 사람의 부모를 알아냄
// 진실을 알고 있는 사람을 입력 받을 때 parent[num]에 num을 넣었기 때문에 값이 같다면 진실을 알고 있다는 것
if (parent[num] == num) {
return false;
}
}
return true;
}
// x가 속하는 부모 원소(최상위 원소)를 찾음
public static int find(int x) {
// parent가 0으로 초기화 되어있기 때문에 parent[x] == 0 조건을 추가
if (parent[x] == 0 || parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]);
}
}
// 두 개의 노드가 속한 집합을 합침(연결함)
public static void union(int x, int y) {
// 각 원소의 최상위 원소를 찾음
x = find(x);
y = find(y);
// 최상위 원소가 같지 않을 경우 union
if (x != y) {
// 진실을 아는 사람이 있을 경우 : 같은 파티에 있기 때문에 진실을 모르는 사람의 부모를 진실을 아는 사람이 되게 함
if (x == parent[x]) {
parent[y] = x;
} else {
parent[x] = y;
}
}
}
}
GITHUB
https://github.com/MinchaeGwon/BOJ/blob/master/BOJ%231043/src/Main.java
Author And Source
이 문제에 관하여([백준 - java] 1043번 : 거짓말), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minchae75/백준-java-1043번-거짓말저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)