[BOJ] 1613 - 역사
문제 링크
문제 설명
역사 사건의 전후를 파악하려고 한다. 일부 사건의 전후 관계가 주어질때, 특정 사진의 전후 관계를 파악하라.
입력
첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
출력
s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.
문제 풀이
전후사건이라고 해서 오 이번주에 공부한 위상정렬 써먹는 문젠가?! 했는데 cyclic graph기 때문에 위상정렬을 써먹을 수는 없다. 모든 노드에서 모든 노드까지 가는 최단 거리를 구하는 플로이드-워셜 알고리즘을 사용하면 쉽게 풀 수 있다.
graph[a][b] : a->b까지 갈 수 있으면 0, 없으면 INF
import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)
n, k = map(int, input().split())
events = [[] for _ in range(n+1)]
graph = [[INF]*(n+1) for _ in range(n+1)]
answer = []
#자기 자신에서 자기 자신으로 가는 경우
for i in range(1, n+1):
graph[i][i] = 0
for _ in range(k):
a, b = map(int, input().split())
graph[a][b] = 0
for i in range(1, n+1):
#각각의 노드에 대해 거쳐가는 경우
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][i]+graph[i][b])
s = int(input())
for _ in range(s):
a, b = map(int, input().split())
if graph[a][b] == 0:
#a->b
answer.append(-1)
elif graph[b][a] == 0:
#b->a
answer.append(1)
else:
answer.append(0)
for a in answer:
print(a)
구현 자체는 어렵지 않은데 플로이드-워셜을 써먹어야 겠다고 생각하내는게 어려웠다.
Author And Source
이 문제에 관하여([BOJ] 1613 - 역사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@woo0_hooo/BOJ-1613-역사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)