BOJ #7 : [G3 | 1375] 나이 (python)

모두에게 속여왔지만 사실 김지민은 한국의 최고령이다.

지민이는 자신이 나이가 가장 많다는 사실을 알고있지만, 다른 사람들의 나이는 몇 살인지 알지 못한다.

하지만 지민이에게는 최고령자로써의 특별한 능력이 있어서 어떤 두 사람을 보면 누가 더 나이가 많은지 알 수 있다.

이 사기적인 능력을 언제나 사용하면 좋겠지만, 지민이가 너무 늙은 나머지 여러 번 사용하면 힘에 부치기 때문에 m번만 사용하려고 한다.

n명의 사람들이 있다. 지민이는 이 사람들 중에서 두 명을 뽑아 나이를 비교하는 것을 m번 할 수 있다.

그 이후, 어떤 두 사람사이의 나이 관게를 파악하고자 한다. 만약 민식이보다 유진이가 나이가 높고 유진이보다 지민이가 나이가 높다면 민식이보다 지민이가 나이가 높다는 것을 알 수 있을것이다.

우리는 위와 같은 방법을 이용해서, 두 사람의 나이를 비교하고 싶다.
BOJ 1375 : 나이

풀이 과정

뭔가 보자마자 위상정렬로 풀어야 될 것 같아서 풀이를 시작했다.
하지만 서로 비교할 수 없는 경우도 있어서 그때그때 bfs를 도는 방식으로 해결했다.

코드

import sys
from collections import deque, defaultdict

input = sys.stdin.readline


def solve():
    N, M = map(int, input().split())

    adj = defaultdict(list)
    for _ in range(M):
        a, b = input().split()
        adj[b].append(a)

    def bfs(i):
        q = deque()
        q.append(i)

        visit = defaultdict(bool)
        res = set()
        while q:
            e = q.popleft()
            res.add(e)
            for nxt in adj[e]:
                if visit[nxt]:
                    continue
                visit[nxt] = True
                q.append(nxt)
        return res

    data = dict()

    result = []
    Q = int(input())
    for _ in range(Q):
        a, b = input().split()
        if a == b:
            result.append("gg")
            continue
        if a not in data:
            data[a] = bfs(a)
        if b not in data:
            data[b] = bfs(b)

        if b in data[a]:
            result.append(b)
        elif a in data[b]:
            result.append(a)
        else:
            result.append("gg")
    print(*result)


solve()