1613(역사) - pypy해결

역사

 

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

 

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

 

출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

---

플로이드 와샬 알고리즘을 사용하는 문제였다.

해당 알고리즘은 큰 어려움이 없는 알고리즘이라 검색을 통해 확인한 후 구현하였다.

해당 알고리즘의 핵심은 경로를 이어 줄 수 있다는 것. 이를 활용하여 문제를 풀었다.

해당 문제에서 특정 구간만 이어져있지만 그 구간을 이으면 다른 구간도 갈 수 있다는 것을 플로이드 와샬 알고리즘을 활용하였다.

 

최단 경로 찾는 알고리즘 비교 (BFS, 다익스트라, 벨만포드, 플로이드 와샬)

BFS	다익스트라	벨만포드	플로이드 와샬
가중치가 있는 그래프 불가능	가중치가 모두 다른 그래프 가능	가중치가 모두 다른 그래프 가능	가중치가 모두 다른 그래프 가능
가중치 없고 모두 동일한 중요도를 가져야 함	가중치가 양의 정수일 때만 가능하다.	가중치가 음의 정수일 때도 가능하다.	가중치가 음의 정수일 때도 가능하다.(단, 음의 사이클이 없어야 한다.)
큐 사용	우선순위 큐 사용	Dynamic Programming 방식 distance[n] = min(distance[n], distance[m] + E(m, n))	Dynamic Programming 방식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j]) 이차원 배열(행렬) 사용
O(E)	우선순위 큐를 사용할 경우 O(ElogV) 플로이드 처럼 모든 정점-모든 정점 최단 경로를 구할 경우 O(V * ElogV)	O(VE)	3중 for문을 사용하므로 O(V^3)
하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 1:N	하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 1:N	하나의 특정 정점에서 다른 정점들까지의 최단 경로를 구함 1:N	모든 정점들간의 쌍에 대해 최단 경로를 한번에 구함 즉 모든 정점들간의 최단 경로를 모두 구한다.N:M

 

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
# 맵 만들기
maps = [[0] * (n+1) for _ in range(n+1)]
# 해당 구간들 이어주기
for _ in range(k):
    a, b = map(int,input().split())
    maps[a][b] = 1

s = int(input().strip())
# 플로이드 와샬 알고리즘 적용
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            # 원래 갈수 있거나 해당 구간을 거쳐서 갈 수 있다면 이어주기
            if maps[i][j] == 1 or maps[i][k] + maps[k][j] == 2:
                maps[i][j] = 1

# 해당 구간들이 이어져있는지 확인
for _ in range(s):
    a, b = map(int,input().split())
    # 정방향으로 이어진 구간
    if maps[a][b] == 1:
        print(-1)
    # 역방향으로 이어진 구간
    elif maps[b][a] == 1:
        print(1)
    # 이어지지 않은 구간
    else:
        print(0)