[백준] 1043. 거짓말 - 파이썬
[Gold IV]
https://www.acmicpc.net/problem/1043
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
이 문제.. 풀고 보니 Union-Find(Disjoint Set)을 이용해 풀 수 있는 문제였다.
근데 그냥 Set 이용해서 풀린 문제.. ^ㅁ^
최대 수가 50이라 TLE가 날 일이 별로 없었기에 가능하지 않았나 싶다.
아마 Set의 intersection()과 union()을 이용해서 시간 단축이 좀 된 것 같다.
Union-Find를 이용한 풀이가 궁금한 분들은 다른 블로그를 검색해 보시는 것을 추천.
풀이 1
처음에는 DFS, Backtracking의 느낌으로 접근하려고 했다.
그런데 문제를 잘못 생각한 부분이 하나 있었다.
진실을 알고 있는 사람을 제외하고는 거짓말이 모든 사람에게 한 번씩만 허용되는 것인 줄 알았는데,
진실을 알고 있는 사람이 아닌 이상, 그 사람이 참석한 모든 파티에서 거짓말을 한다면, 그 사람에게는 들키지 않는다는 것..!
WA.
N, M = map(int, input().split())
T = [*map(int, input().split())]
T_num = T[0] # 진실을 아는 사람 수
T = T[1:] # 진실을 아는 사람들의 번호 리스트
member = []
for _ in range(M):
A = [*map(int, input().split())][1:]
# 진실을 아는 사람이 있는 파티는 아예 제외해버리기
for i in T:
if i in A:
continue
member.append(A)
max_depth = len(member)
result = 0
def dfs(P: dict, n: int, cnt: int):
global result
if cnt > result:
result = cnt
if n == max_depth:
return
# 파티에서 거짓말을 하지 않을 경우와
dfs(P.copy(), n+1, cnt)
# 파티에서 거짓말을 하는 경우
for i in member[n]:
if P.get(i, -1) != -1:
return
P[i] = 0
dfs(P.copy(), n+1, cnt+1)
dfs({}, 0, 0)
print(result)
풀이 2
line 13 ~ 19의 반복문에서, 1차적으로 진실을 아는 사람과 같이 파티를 참석한 사람들을 모두 진실을 아는 사람으로 set에 저장한다. 이 과정에서 진실을 아는 사람이 없는 파티를 Queue에 추가한다.
앞의 반복문에서는, 뒤에 진실을 알게 된 사람이 생기더라도, 처리해주지 못한다.
예를 들면, 처음 진실을 아는 사람이 [1] 이고, 아래와 같은 input이 들어오면,
2 2 3
2 1 3
두 번째 파티에서, 3도 진실을 알게 되므로, 첫번째 파티의 2도 결국 진실을 아는 사람이 되는 것인데, 이를 처리해주지 못한다.
따라서 line 21 ~ 27의 반복문에서, 이중 반복문을 돌려 이러한 경우를 모두 처리해 준다.
그 이후, 마지막 반복(line 30~32)에서, 진실을 아는 사람이 없는 파티는 모두 거짓말을 할 수 있는 파티이므로, 그 개수를 센다.
그것이 곧 답.
AC.
from collections import deque
N, M = map(int, input().split())
T = [*map(int, input().split())]
T_num = T[0] # 진실을 아는 사람 수
T = T[1:] # 진실을 아는 사람들의 번호 리스트
T = set(T)
result = 0
parties = deque()
for _ in range(M):
A = set([*map(int, input().split())][1:])
# 진실을 아는 사람이 있는 파티의 사람들은 모두 진실을 알게 되는 것(진실을 들으므로, 다음 번에 거짓을 들으면 들통남.)
if len(T.intersection(A)) >= 1:
T = T.union(A)
else:
parties.append(A)
for _ in range(len(parties)):
for _ in range(len(parties)):
p = parties.popleft()
if len(T.intersection(p)) >= 1:
T = T.union(p)
else:
parties.append(p)
for party in parties:
if len(T.intersection(party)) == 0:
result += 1
print(result)