[Baekjoon Online Judge] 백준 1613번 역사(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1613번 역사

(Python)

(글쓴날 : 2020.06.14)

 

---

* Baekjoon Online Judge, 백준 1613번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1613번 역사

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1613

1613번: 역사

---

2) 풀이 과정

* 시간 복잡도 : O(EV²)

 

역사적 사건들의 일부 전후 관계가 주어질 때, 주어지지 않은 전후 관계를 유추할 수 있을지 확인하는 문제입니다.

단, 앞 순서의 사건이 먼저 일어났을 시 -1, 뒷 순서의 사건이 먼저 일어났을 시 1, 순서를 유추할 수 없을 시 0을 출력합니다.

 

저의 경우, 플로이드 와샬 알고리즘을 적용했으며, Python을 사용했습니다.

주어진 사건의 전후 관계들을 인접 행렬로 구현한 뒤, 플로이드 와샬 알고리즘을 적용하여 유추할 수 있는 사건들을 기록해 문제를 해결했습니다.

예를 들어, 1번 사건 이후에 2번 사건이 일어났고, 2번 사건 이후에 3번 사건이 일어났다면, 1번 사건이 3번 사건 보다 먼저 일어났고, 3번 사건이 1번 사건 보다 늦게 일어났음을 유추해 낼 수 있으며, 이러한 일련의 순서를 그래프의 경로 문제로 변환하여 접근이 가능합니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
def floydWarshall():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if adjMatrix[i][k] and adjMatrix[k][j]:
                    adjMatrix[i][j] = 1
 
 
N, K = map(int,input().split())
adjMatrix = [[0] * N for _ in range(N)]
 
for _ in range(K):
    a, b = map(int,input().split())
 
    adjMatrix[a-1][b-1] = 1
 
floydWarshall()
 
s = int(input())
 
for _ in range(s):
    a, b = map(int,input().split())
    
    if adjMatrix[a-1][b-1] == 1:
        print(-1)
    elif adjMatrix[b-1][a-1] == 1:
        print(1)
    else:
        print(0)

---