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

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

1613번: 역사

 

여러개의 순서 조건이 등장하는게 마치 위상정렬을 써야할 것 같았는데

연관이 되지 않은 그룹이 두 개 이상 있을 때 판단할 수가 없단걸 생각하지 못했다.

왜냐면 위상정렬은 정렬 결과 1차원배열일 것이기 때문에.

 

플로이드 워셜 알고리즘이 어차피 출발지점에서 어느 지점을 건너 도착지점까지 가는걸

갱신하면서 최단거리를 구하는거라

비슷하게 생각하면 갱신이 됐다? -> 이어져있다 라는걸 이용해서 풀면 됐다.

 

플로이드 워셜 알고리즘을 통과하고 나면 만약 1 -> 2, 2 -> 4 처럼 1 -> 4 이렇게 이어지지 않았어도

graph[1][4] 의 값은 1가 되어있을 것.

그 의미는 4 라는 사건이 일어나기 전엔 1를 통과해야 한다는 의미다.

 

근데 그 역방향을 어떻게 생각해야하는건지 잘 모르겠어서

구글링의 힘을 좀 빌렸다,,

너무 간단했다. 1가 4보다 먼저 발생했느냐를 묻는다면

당연히 1 -> 4 가 이어진 상태니까, 즉 1 가 4보다 먼저 일어난거니까 -1을 출력하면 되는거고

4가 1보다 먼저 발생했느냐를 따질땐 그냥 4 -> 1 가 이어진 상태냐? 를 물으면 되는거였다.

 

풀이 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
graph = [[0 for i in range(N+1)] for i in range(N+1)]

for i in range(K):
    a, b = map(int, input().split(" "))
    graph[a][b] = 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] and graph[k][j]:  # 거쳐갈 수 있는 길이 있으면
                graph[i][j] = 1

qn = int(input())
for i in range(qn):
    before, after = map(int, input().split(" "))
    if graph[before][after] == 1:
        print(-1)
    elif graph[after][before] == 1:
        print(1)
    else:
        print(0)

# 위상정렬을 사용해봤으나 연관 없는 두 그룹을 비교하는게 불가능하다는걸 깨달음
# after -> before 가는걸 graph[after][before] 로 판별할 수 있다는걸 생각하지 못했네..
# https://www.acmicpc.net/problem/1613