(Python) - BOJ(1613번) : 역사

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

1613번: 역사

---

• 문제 : 

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

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

 

 

 

---

• 풀이 :

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

출발지 i 목적지 j로 가는 경로를 찾으며 사이에 k를 경유해서 진행이 가능할 경우도 체크해 주었습니다.

 

 

우선, 제 코드가 아무리 수정해도 시간초과에러가 나서 풀이를 찾아본 코드를 첨부합니다.

 

 

내 코드

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
cost = [[0]*N for _ in range(N)]

for _ in range(K):
    a,b = map(int,input().split())
    cost[a-1][b-1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if cost[i][k] and cost[k][j]:
                cost[i][j] = 1

for _ in range(int(input())):
    i,j = map(int,input().split())
    if cost[i-1][j-1] == 1:
        print(-1)
    elif cost[j-1][i-1] == 1:
        print(1)
    else:
        print(0)

 

풀이를 찾아본 코드

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)

 

 

함수화를 제외하고 거의 동일한 코드인데 제 코드에서만 시간초과가 나는 것을 보니 무언가 파이썬 실행시간 계산에 미숙한 것 같습니다.  공부를 더 해야겠습니다.

혹시나 이유를 아시는분은 댓글에서 알려주시면 감사하겠습니다. :)