[백준] 1613 역사

---

각 사건 중 순서를 알고있는 경우가 주어지고, 주어진 테스트 케이스에서 순서를 판별하는 문제이다.

 

보통 일의 순서를 알아내는 방법으로는 위상정렬이 존재하기 때문에 위상정렬을 먼저 시도했었지만 해결하지 못했다. 그리고 사건의 순서에 대한 정방향 그래프와 역방향 그래프를 그려 DFS를 사용하였으나 시간초과로 인해 해결하지 못하였다(시간 초과를 제외하면 해결 됐을 거라 생각한다).

 

결국 문제의 분류를 보게 되었는데 플로이드-와샬로 분류되어있었다. 전혀 플로이드-와샬 알고리즘으로 접근할 생각 조차 하지 못했기 때문에 몇시간이 주어져도 해결하지 못했을 것이다. 일의 순서를 판별하는 문제에 최단거리 알고리즘도 사용이 가능하다는 것을 새겨 놓아야겠다.

 

플로이드-와샬 알고리즘을 사용하여 문제를 해결 할 수 있는 이유는 다음과 같다.

• map[first][second] = -1, map[second][first] = 1로 초기화한다. 이는 first가 second에 선행하며(-1), second가 first에 후행한다는 뜻이다. 
• 반복문을 돌며 map[i][j] == 0인 경우 순서를 먼저 판별한다. 이는 순서가 명시되지 않았을 때 판별 가능한 경우에 한하여 순서를 판별하겠다는 뜻이다.
  • map[i][k] == -1 and map[k][j] == -1 인 경우 map[i][j] = -1로 한다. i 사건이 k사건 보다 선행하고, k 사건이 j 사건보다 선행하면 i 사건이 j 사건보다 선행한다는 뜻이다.
  • map[i][k] == 1 and map[k][j] == 1 인 경우 map[i][j] = 1로 한다. i 사건이 k 사건 보다 후행하고, k 사건이 j 사건보다 후행하면 i 사건이 j 사건보다 후행한다는 뜻이다.

from sys import stdin

readline = stdin.readline


def floyd_warshall():
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if _map[i][j] == 0:
                    if _map[i][k] == 1 and _map[k][j] == 1:
                        _map[i][j] = 1
                    elif _map[i][k] == -1 and _map[k][j] == -1:
                        _map[i][j] = -1

if __name__ == "__main__":
    n, k = map(int, readline().split())
    _map = [[0] * n for _ in range(n)]

    for _ in range(k):
        u, v = map(int, readline().split())
        _map[u-1][v-1] = -1
        _map[v-1][u-1] = 1 

    floyd_warshall()
    t = int(readline().strip())
    
    for _ in range(t):
        start, end = map(int, readline().split())
        start -= 1
        end -= 1

        print(_map[start][end])