문제 링크
https://www.acmicpc.net/problem/1043
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
접근 방식
처음에는 파티 참석자들을 순회하면서 진실을 알고 있는 사람과 같이 파티에 참석했다면,
그 참석자들도 진실을 알고 있는 사람들 집합에 추가해주었다.
그치만 이 방식은 파티에 참석하는 순서에 따라 반례가 생길 수 있다 ..!
이 부분에서 계속 삽질함
예를 들어 참석자는 4명이고 1번만이 진실을 알고 있다고 하자.
각 파티의 참석자들이 (2,3), (3,4), (1,2) 라고 했을 때, 처음 생각했던 풀이에서는
1번과 2번만이 진실을 알고 있는 집합에 추가되게 된다.
하지만 문제에서는 (1,2) 번이 참여한 파티에서 지민이는 진실을 말해야 하고,
그렇다면 (2,3)번이 참석한 파티, (3,4)번이 참석한 파티 역시 진실을 말해야 해서 결국 거짓말을 할 수 있는 파티의 개수는 0이 된다.
내가 처음 생각한 방식에서는 1번 거짓말이 가능하다고 결과가 나올 것이다.
현재 구조가 바이러스 퍼지듯이 진실을 들은 사람들이 퍼져나가는 구조이기 때문에 집합으로 묶어야겠다고 생각했다.
진실을 알고 있는 집합과, 진실을 모르는 집합으로 나누자 ! 가 핵심이라고 생각된다.
이렇게 부분집합을 나누는 알고리즘으로는 Union-find 가 있다.
문제를 해결한 과정은 아래와 같다.
- 진실을 알고 있는 사람들의 parent 배열의 값을 0으로 한다.
- 동일한 파티에 참석하는 사람들을 union 해준다. (첫번째 for loop)
- 파티에 참석한 사람들 중 parent 값이 0인 사람이 있으면 그 파티는 진실을 말해야 하는 파티 !
풀이 코드
import sys
def input():
return sys.stdin.readline()
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
a = find(a)
b = find(b)
if a < b:
parent[b] = a
else:
parent[a] = b
N, M = map(int, input().split())
parent = [i for i in range(N+1)]
truth = list(map(int, input().split()[1:]))
for t in truth:
parent[t] = 0
parties = []
for m in range(M):
tmp = list(map(int, input().split()))
parties.append(tmp[1:])
for p in range(len(parties[m]) - 1):
union(parties[m][p], parties[m][p+1])
ans = 0
for m in range(M):
flag = True
for p in parties[m]:
if parent[find(p)] == 0:
flag = False
break
if flag:
ans += 1
print(ans)삽질의 흔적..
끝.