[백준] 1043. 거짓말 - python3

1043. 거짓말

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

1043번: 거짓말

 

 

내 풀이 1 - 실패

 

처음에는 그냥 단순하게

진실을 아는 사람을 포함해서 함께 있는 파티원들은 다 한묶음으로 생각했다.

배열을 이용해서 해당 사람들은 값을 1 로 표시해두고

다시 파티 목록을 확인하며 파티원 모두가 0 일 때만 answer + 1 해줬다.

 

하지만 틀렸다고 나와서 어떤 반례가 있을까 생각해보니

모든 연결고리를 찾지 못해서 그랬다.

 

10 9
4 1 2 3 4
2 1 5
2 2 6
1 7
1 8
2 7 8
1 9
1 10
2 3 10
1 4

 

이 예제에서 7 이나 8 이 진실을 아는 사람과 함께라는 가정을 추가하면 제대로 업데이트 되지 않는다.

 

10 10
4 1 2 3 4
2 1 5
2 2 6
1 7
1 8
2 7 8
2 1 7	# 추가
1 9
1 10
2 3 10
1 4

 

추가된 부분에서 7 은 진실을 아는 사람이 되므로

바로 전 파티에서 함께 있던 8 도 진실을 아는 사람으로 업데이트 해줘야하지만

내 처음 구현방식으로는 되지 않는다.

 

그래프 BFS 를 이용하거나 Union&Find 를 이용해야 할 것 같다.

 

 

다른 사람의 풀이 - Union & Find

from sys import stdin

def find(parent, x):
    if x != parent[x]:
        parent[x] = find(parent, parent[x])

    return parent[x]

def union(parent, a, b, people):
    a = find(parent, a)
    b = find(parent, b)

    if a in people and b in people:
        return

    if a in people:
        parent[b] = a
    elif b in people:
        parent[a] = b
    else:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b

N, M = map(int, stdin.readline().split())
people = list(map(int, stdin.readline().split()))[1:]
party = []
parent = list(range(N+1))
answer = 0

for m in range(M):
    n = list(map(int, stdin.readline().split()))
    p = n[1:]
    for i in range(n[0]-1):
          union(parent, p[i], p[i+1], people)
    party.append(p)
    
for i in range(len(party)):
    for j in range(len(party[i])):
          if find(parent, party[i][j]) in people:
                break
    else:
      answer += 1

print(answer)

 

Union & Find 를 이용한 풀이

 

 

 

다른 사람의 풀이

from sys import stdin

N, M = map(int, stdin.readline().split())
people = set(map(int, stdin.readline().split()[1:]))
party = []
answer = 0

for m in range(M):
    n = list(map(int, stdin.readline().split()))
    party.append(set(n[1:]))
  
for m in range(M):
      for i in range(len(party)):
            if party[i] & people:
                  people = people.union(party[i])
    
for i in range(len(party)):
    if party[i] & people:
          continue
    answer += 1

print(answer)

 

set 의 union 함수를 이용해 구하는 방식

union 대신 | 연산을 하기도 함