[백준] 1043번 거짓말 - 파이썬(Python)

문제 (링크)

 

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

1043번: 거짓말

 

나의 코드

import sys
input = sys.stdin.readline

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

    return parent[x]

# 사실을 아는 사람과 Union시, 해당 사람이 부모노드가 되도록
def union(parent, a, b, know_truth):
    a = find(parent, a)
    b = find(parent, b)

    if a in know_truth and b in know_truth:
        return

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


n, m = map(int, input().split())
know_truth = list(map(int, input().split()))[1:]

parties = []
parent = list(range(n+1))

for _ in range(m):
    party_info = list(map(int, input().split()))
    party_len = party_info[0]
    party = party_info[1:]
    
    for i in range(party_len - 1):
        union(parent, party[i], party[i+1], know_truth)
    
    parties.append(party)
    
ans = 0
for party in parties:
    for i in range(len(party)):
        if find(parent, party[i]) in know_truth:
            break
    
    else:
        ans += 1

print(ans)

 

코드 설명 및 풀이법

처음에는 단순하게 파티 정보를 반복문으로 돌면서, 해당 파티에 이미 사실을 알고 있는 사람이 존재한다면, 해당 파티에 있는 모든 사람들을 사실을 아는 사람 배열에 추가해주는 로직을 생각했다.

 

하지만, 그런 방식으로 하게되면 파티 정보가 나열되는 순서에 따라서 오류가 발생할 수 있다.

 

위의 5번 입출력 예제를 살짝만 꼬아보자.

 

파티에 대한 정보인 3번째 줄부터 확인하자.

 

2 1 5

2 2 6

1 7

1 8

2 7 8

1 9

1 10

2 3 10

1 4

 

다음과 같이 입력이 들어올 때, 앞서 말한 로직대로 사실을 아는 사람에 대한 배열을 업데이트 할 경우,

 

초기에 입력 받은 1, 2, 3, 4번에 더하여 5, 6, 10번이 추가된다.

 

그리고 이 중간에 정보가 하나 더 추가된다고 가정해보자.

 

2 1 5

2 2 6

1 7

1 8

2 7 8

1 1 7

1 9

1 10

2 3 10

1 4

 

다음과 같이 1 1 7 이라는 정보가 추가되면, 초기에 입력받은 1, 2, 3, 4에 더해 5, 6, 10, 그리고 7이 추가로 더해진다.

 

그렇다면 이 예시에서 정말 사실을 아는 사람은 1, 2, 3, 4, 5, 6, 7, 10 뿐일까?

 

그렇지 않다.

 

8번 역시 1 1 7이라는 정보가 추가되기 전에 2 7 8의 정보에서 7번과 8번이 동일한 파티에 있기 때문에 사실을 알게되지만, 이 정보는 업데이트 되지 않는다.

 

다시 말해, 내가 처음에 생각한 로직은 입력 순서에 의해 영향을 받았다.

 

따라서, 순서에 영향받지 않는 다른 알고리즘을 사용할 필요가 있었고, Union-Find 알고리즘을 사용했다.

 

Union-Find 알고리즘을 통해 구현하고자 했던 목표는 다음과 같다.

 

1. 동일한 파티에 참석하는 사람들을 Union 한다.

2. 만약 Union하려는 대상 중 사실을 알고 있는 사람이 있다면, 해당 사람을 Parent로 한다.

3. 만약 두 대상이 모두 사실을 알고 있다면, 연결하지 않는다.

4. 각 파티에 대한 정보를 돌면서, 해당 파티에 참여하는 사람 중 Parent가 사실을 알고 있는 사람 목록에 있다면 해당 파티에선 진실을 이야기하는 것으로 간주한다.

 

위 단계를 적절히 구현한다면 정답을 받을 수 있는 문제이다.