[골드 3] 백준 1613 - 역사 (파이썬)

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

풀이

• N: 사건 개수 (노드 수), K: 사건 간 전후관계의 개수 (방향 그래프 간선)
• 각 입력 (a, b)는 a 사건이 b 사건보다 먼저 일어났음을 의미 → 단방향 간선
• S개의 질문: a와 b 중 누가 먼저인지 판단

먼저 입력 처리 및 인접리스트를 구현한다.

adj = [[] for _ in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append(b)

방향 그래프 형태로 인접 리스트를 구성한다.

모든 정점에서 BFS를 돌려 도달 가능한 노드를 기록한다.

visit = [[False] * N for _ in range(N)]
for i in range(N):
    queue = deque()
    queue.append(i)
    visit[i][i] = True

    while len(queue) != 0:
        u = queue.popleft()

        for v in adj[u]:
            if not visit[i][v]:
                queue.append(v)
                visit[i][v] = True

visit[i][j] == True 는 i에서 j로 도달 가능함을 의미하며, BFS로 i번 사건에서 도달 가능한 모든 사건 j를 찾아 기록한다.

마지막으로 질의에 따라 출력한다.

if visit[a][b]:
    print("-1")
elif visit[b][a]:
    print("1")
else:
    print("0")

• a -> b 도달 가능하면 -1
• b -> a 도달 가능하면 1
• 둘 다 아니면 0 (알 수 없음)

코드

# 백준 1613 - 역사
# 분류 : BFS

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
adj = [[] for _ in range(N)]

for _ in range(K) :
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    adj[a].append(b)

visit = [[False] * N for _ in range(N)]
for i in range(N) :
    queue = deque()
    queue.append(i)
    visit[i][i] = True

    while len(queue) != 0 :
        u = queue.popleft()

        for v in adj[u] :
            if not visit[i][v] :
                queue.append(v)
                visit[i][v] = True

S = int(input())
for _ in range(S) :
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    if visit[a][b] :
        print("-1")
    elif visit[b][a] :
        print("1")
    else :
        print("0")