[PS] BOJ 1613 / 역사

Minjun Kim

21 Oct 2025 • 2 min read

Thumbnail: Photo by Luobing (Unsplash)

문제 링크: https://www.acmicpc.net/problem/1613

플로이드-워셜을 통해 모든 정점들 사이의 연결 관계를 파악하는 문제입니다.

풀이

플로이드-워셜

오랜만에 푸는 플로이드-워셜 문제인 만큼, 개념을 다시 정리해 봅시다.

플로이드-워셜은 모든 정점에서 다른 모든 정점으로의 최단 경로를 계산하는 알고리즘입니다. 3중 반복문으로 동작하기 때문에, $V$개의 정점에 대해, 시간 복잡도는 $O(V^3)$입니다.

graph = [[INF for _ in range(N + 1)] for _ in range(N + 1)]
... # 그래프 입력

# 플로이드-워셜
for mid in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if graph[i][mid] + graph[mid][j] < graph[i][j]:
                graph[i][j] = graph[i][mid] + graph[mid][j]

플로이드-워셜 구현

문제 풀이

이 문제는 유향 그래프에서 각 정점이 어떻게 연결되었는지 판단하는 문제입니다. 두 사건(정점)간의 연결 관계를 파악하면 되는데, $S$번 파악해야 하므로 한 번에 모든 정점 간의 연결 관계를 파악하는 편이 효율적입니다.

따라서, 플로이드-워셜 알고리즘을 통해 $N$개의 정점들 간의 상호 연결 관계를 미리 계산해줍니다. 이후, $S$개의 질문에 대해 다음과 같이 계산합니다:
두 정점 $s, e$에 대해

s -> e로 연결되어 있을 때 (graph[s][e]가 INF보다 작을 때)
- s가 e보다 먼저 일어난 사건이므로 -1을 출력합니다.
e -> s로 연결되어 있을 때 (graph[e][s]가 INF보다 작을 때)
- s가 e보다 나중에 일어난 사건이므로 1을 출력합니다.
그 외의 경우, 두 정점은 연결되지 않았으므로 우선 관계를 파악할 수 없습니다.
따라서 0을 출력합니다.

전체 코드

input = open(0).readline
N, K = map(int, input().split())
INF = 500000

graph = [[INF for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(K):
    s, e = map(int, input().split())
    graph[s][e] = 1

for mid in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if graph[i][mid] + graph[mid][j] < graph[i][j]:
                graph[i][j] = graph[i][mid] + graph[mid][j]

for _ in range(int(input())):
    s, e = map(int, input().split())
    if graph[s][e] < INF:
        print("-1")
    elif graph[e][s] < INF:
        print("1")
    else:
        print("0")

solution.py