[백준 1043 C++] 거짓말

오늘은 백준(BOJ) 1043번 거짓말 문제에 대해 다뤄볼 예정이다.

미확인 도착지 문제 링크 (백준(BOJ) 1043번 문제): https://www.acmicpc.net/problem/1043

1043번: 거짓말

문제 설명 

백준 1043번 거짓말 문제는 지민이가 각 파티에서 자신의 이야기의 진실을 알고 있는 사람이 있을 경우, 이야기를 과장되게 할 수 없으므로 이야기의 진실을 모르고 있는 사람들만 모인 파티의 최대 개수를 세는 문제이다. 즉, 다시 말해 파티 1에 [사람 1 (진실 앎), 사람 2, 사람 3] 이와 같이 파티를 열게 되면 사람 2, 사람 3도 진실을 알게 되기에 이야기를 과장할 수 없게 되어, 사람 2, 사람 3이 속한 파티에서 이야기를 과장할 수 없게 된다. 

문제 풀이

백준 1043번 거짓말 문제는 각 집합을 나눠야하는 작업을 해주어야 하기 때문에 UnionFind 알고리즘으로 풀 수 있으며, 시간이 2초로 잡혀있어 DFS 알고리즘으로도 풀 수 있다. 하지만, 쓴이는 UnionFind 알고리즘으로 문제를 해결하였다. 

 

처음 문제를 풀고 난 후, 예제 케이스는 다 통과 했었지만 반례(Conuter Example)로 아래와 같은 입력의 결과가 2가 나왔었다. 

Counter Example:

4 5

1 1

1 1

1 2

1 3

2 4 2

2 4 1

Result: 1

처음 위 예제를 입력 하였을 때, ID 배열이 1 2 3 1 이와 같이 나와서 답이 2가 나왔던 것이다. 

이 문제의 핵심은 그룹을 비교할 때, 루트 노드 간에 비교를 해주어야 하는 것이었다. 

 

위 내용에 대한 소스코드는 아래와 같고, 86번 째 줄이 핵심이라고 볼 수 있다.