[BOJ][Python]1043 풀이

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

1043번: 거짓말

from collections import deque
import sys
ssr = sys.stdin.readline

def check_truth():
    while q:
        p = q.popleft()
        for party in parties:
            if p in party[1:]:
                for i in party[1:]:
                    if visited[i] == False:
                        q.append(i)
                        visited[i] = True
    
n, m = map(int, ssr().split())
knowing_truth = list(map(int, ssr().split())) # 0 : num of person, 1~ : person's num
visited = [False for _ in range(n+1)]
q = deque([])
for i in knowing_truth[1:]:
    visited[i] = 1
    q.append(i)
parties = [list(map(int, ssr().split())) for _ in range(m)]
check_truth()
for party in parties:
    for i in party[1:]:
        if visited[i] == 1:
            m -= 1
            break
print(m)

다른 걸 하다보니 오늘은 좀 늦었습니다. 꽤 오래 클래스 3에 머물렀는데 이 문제로 이제 클래스 4가 되었네요. 데이크스트라 때문에 긴 시간 멈춰있다 이제 시동이 걸린 느낌이라 뿌듯하긴 합니다만, 저번에 데이크스트라를 풀어서 그런지 오늘은 그렇게 감동이 크지 않네요(이번 문제가 그렇게 어렵지 않아서 그런 것도 있는 것 같습니다). 클래스 3 일 때에 비해 저는 성장했으려나요. 알고리즘 방면에서 기뻐할만한 성과가 있기는 했습니다만 사실 남들과 비교했을 때는 아직 출발선에 서지도 못한 정도 인 것 같아요. 알고리즘 이외의 부분에서도 성장을 하긴 했습니다만, 스스로 자신감을 가질만한 성과인지는 모르겠습니다. 분명히 예전에 비해 데이터사이언스나 인공지능과 관련된 지식이 늘긴 했지만 그런 지식들이 완전히 제 것이 되었는지는 잘 모르겠습니다. 예전에 비해 더욱 더 두루뭉실하게 많이 알게되긴 했지만 정작 핵심적인 내용을 누가 묻는다면 더듬거리면서 대답하는 정도가 아닐까요. 항상 어떤 이벤트가 있는 날이면 말이 많아지는 것 같습니다. 이 쯤하고 풀이를 진행해보죠.

 

이 문제는 사실 그렇게 어렵지는 않습니다. 지민이는 모든 파티에 가서 얘기를 할건데 그 얘기에 대한 진실을 알고 있는 사람이 입력으로 주어집니다. 그 사람 & 그 사람과 같이 있는 사람에게는 진실만을 말해야 합니다. 또한 그 사람과 같이 있을 일이 있는 사람한테도 진실만을 말해야 해요. 입력으로 주어진 파티는 참여할 사람들의 명단이 있는 스케줄표라고 생각하면 되겠죠. 문제를 제가 이해하기 쉬웠던 문장으로 풀어서 쓰면, 진실을 아는 사람한테는 진실만을 말해야 하고, 거짓을 아는 사람한테는 거짓만을 말해야 한다가 될 것 같아요. 이게 이해가 잘 안되면 진실을 아는 사람이 자기와 만날 스케줄이 있는 모든 사람에게 이미 진실을 다 전달했다고 생각하면 더 편할 것 같네요.

 

아무튼 처음에 진실을 아는 사람으로 주어진 사람 말고도 다른 사람들도 진실을 알게 되는 경우가 있다는 얘기죠. 그래서 진실을 아는 사람들을 체크해줘야 합니다. 아직은 입력이 별로 안많은건지 위처럼 코드를 좀 비효율적으로 짜도 통과합니다. 파티에 참여하는 인원들 중에서 진실을 아는 사람이 있다면 해당 파티의 전원을 진실을 안다고 표시하고 queue에 추가해서 해당 과정을 반복합니다. 즉, 최악의 경우는 m(m-1)/2 만큼 반복을 하게 되겠네요. 그러고 또 파티 목록을 쭉 돌면서 진실을 아는 사람이 있는지 확인하고 있으면 거짓을 말할 수 있는 파티의 개수(최대 m)에서 1씩 빼서 답을 구하는 겁니다. bfs를 풀 때 사용하는 테크닉을 그대로 사용하긴 했습니다만, 이걸 bfs, 그러니까 그래프 탐색으로 볼 수 있을지는 살짝 애매하네요. 제가 너무 그래프에 대해 경직된 사고방식을 갖고 있는 건가 싶기도 합니다만...

 

알고리즘 분류에 분리 집합이라는 태그가 있던데 근시일내에 해당 내용도 찾아서 한 번 추가해보도록 하겠습니다.

 

추가// 유니온 파인드 알고리즘으로도 한 번 풀어보겠습니다.

import sys
ssr = sys.stdin.readline

def union(node1, node2):
    root1, root2 = find(node1), find(node2)
    if root1 != root2:
        if rank[root1] < rank[root2]:
            uf[root1] = root2
        elif rank[root1] == rank[root2]:
            uf[root1] = root2
            rank[root2] += 1
        else:
            uf[root2] = root1
    
def find(node):
    if uf[node] == node:
        return node
    else:
        uf[node] = find(uf[node])
        return uf[node]

n, m = map(int, ssr().split())
knowing_truth = list(map(int, ssr().split()))
parties = [list(map(int, ssr().split())) for _ in range(m)]
uf = [i for i in range(n+1)]
rank = [0 for _ in range(n+1)]
if knowing_truth[0] != 0:
    for i in knowing_truth[1:]:
        uf[i] = knowing_truth[1]
    rank[knowing_truth[1]] = 1
cnt = 0
for people in parties:
    for i in people[1:]:
        union(people[1], i)
for people in parties:
    if knowing_truth[0] != 0:
        if uf[find(knowing_truth[1])] == uf[find(people[1])]:
            cnt += 1
print(m-cnt)

이 문제는 BFS보다는 유니온 파인드 알고리즘으로 풀었을 때 런타임에 이득이 있습니다. 알고리즘의 구조적 차이 때문인데요. BFS의 경우는 직접적으로 연결이 되어있는 노드를 탐색하는게 용이한 반면에 유니온 파인드는 어떤 그룹에 속해있는지를 판단하는게 용이하기 때문에 그렇습니다. 문제에서 요구하는게 누가 누구한테 진실을 말했는지가 아니라 진실을 아는 그룹과 모르는 그룹을 구분하는 것이기 때문에 진실을 아는 그룹에 누가 포함되어 있는지를 효율적으로 확인할 수록 이득이 생기는 것입니다. 그래서 유니온파인드 알고리즘을 이욯해서 탐색 시간을 줄이는 것이죠. 물론 BFS로 풀어도 통과할 수 있는 넉넉한 문제입니다.