[백준] 1043. 거짓말 - 파이썬

[백준] 1043. 거짓말 - 파이썬

[Gold IV]

 

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

이 문제.. 풀고 보니 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)