백준 1613 역사

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1613

일부 사건들의 전후 관계가 주어질 때, 주어진 사건들의 전후 관계를 구하는 문제

풀이

난이도 : GOLD III

✔ 순서

1. 사건들의 전후 관계를 배열로 1과 -1로 저장한다.
2. 완전탐색으로 배열의 모든 경우의 수를 돌면서 전후 관계를 업데이트한다. (플로이드 워셜)

✔ 내용

이 문제는 플로이드 워셜 알고리즘을 적용하여 풀이하였다.
graph[a][b] 를 a와 b의 사건 전후 관계로 정의하였고, 만약 a가 b보다 먼저 일어난 사건이라면 graph[a][b] = -1 로 저장하였다.

플로이드워셜 알고리즘을 응용하여 i가 k보다 먼저일어난 사건이고, k가 j보다 먼저 일어난 사건이라면 i는 j보다 먼저 일어난 사건이라는 것을 업데이트 해나갔다.
문제에서 n 의 입력 개수를 보면 400이하의 자연수이므로 O(n^3)의 시간이 걸리는 플로이드 워셜 알고리즘의 풀이는 적합하다고 볼 수 있다.

✔ 주의할 점

• 이 문제 풀이는 python3로 제출하면 시간초과가 발생하므로 pypy3로 제출해야 한다.
  

코드

n, k = map(int, input().split())

graph = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(k):
    a, b = map(int, input().split())
    graph[a][b] = -1
    graph[b][a] = 1

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if graph[i][k] == 1 and graph[k][j] == 1:
                graph[i][j] = 1
            elif graph[i][k] == -1 and graph[k][j] == -1:
                graph[i][j] = -1

s = int(input())
for _ in range(s):
    a, b = map(int, input().split())
    print(graph[a][b])