백준 #31937 로그프레소 마에스트로

문제 링크

[31937 로그프레소 마에스트로]

문제 설명

컴퓨터간의 파일 전송기록이 로그로 남아있고 감염된 컴퓨터들이 주어졌을 때, 최초로 감염된 컴퓨터를 찾는 문제

코드

import sys
input = sys.stdin.readline


N, M, K = map(int, input().split())
arr = list(map(int, input().split()))
infected = [False] * (N + 1)
for x in arr:
    infected[x] = True
log = [list(map(int, input().split())) for _ in range(M)]
log.sort(key = lambda x:(x[0]))

for i in range(1, N + 1):
    if not infected[i]:
        continue
    visited = [False] * (N + 1)
    visited[i] = True
    flag = True
    for t, a, b in log:
        if visited[a]:
            if infected[a]:
                if not infected[b]:
                    flag = False
                    break
                else:
                    visited[b] = True
            else:
                flag = False
                break
    for j in range(1, N + 1):
        if visited[j] != infected[j]:
            flag = False
            break
    if flag:
        print(i)
        exit()

풀이

처음 시도할때는 로그 기록만 살피면서 감염 경로에서의 모순이 있는 부분만 찾으려고 했었다. 생각보다 쉽게 안풀리고 계속 틀려서.. $N$범위가 작길래 그냥 감염되어있는 애들 하나하나를 최초의 감염 컴퓨터라 가정하고 모순점을 찾아서 풀었다. 생각보다 엣지케이스가 많은 문제이고 생각할거리도 많은 문제였다.

실제 현업에서도 이렇게 하나하나 다 가정하고 찾는건가..? 더 좋은 방법을 쓰겠지?