[백준 / Python] 1613 역사 (플로이드-와샬 알고리즘)

결과 (PyPy3)

• 메모리: 127824 KB (개선: 126088ms)
• 시간: 5440 ms (개선: 640ms)

주의할 것

• 항상 index 때문에 틀렸습니다 를 한 번 마주친다. 조심하자!!!!

개선

• 시간이 너무 오래 걸려서 몇가지를 개선해보았다.
• 참고: https://www.acmicpc.net/source/18012011
  1. maxsize 대신 0 대입. maxsize는 정말 필요할 때만 쓰자.
     • 시간: 5440ms to 3232ms 🎉
  2. import readline. 그냥 input() 대신 sys.stdin.readline

      import sys
      ip = sys.stdin.readline

     • 시간: 3232ms to 640ms 😇 (이걸 이제까지 몰랐다니)

개선 전 코드

from sys import maxsize

n, k = map(int, input().split()) # 사건의 개수, 알고 있는 사건의 전후 관계의 개수
arr = [[maxsize] * (n + 1) for _ in range(n + 1)]

for _ in range(k):
    a, b = map(int, input().split())
    arr[a][b] = 1

def floyd():
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if arr[i][k] + arr[k][j] == 2:
                    arr[i][j] = 1

floyd()

s = int(input())
for _ in range(s):
    x, y = map(int, input().split())
    if arr[x][y] == 1:
        print(-1)
    elif arr[y][x] == 1:
        print(1)
    else:
        print(0)

개선 후 코드

import sys # 개선
ip = sys.stdin.readline # 개선

n, k = map(int, ip().split()) # 개선
arr = [[0] * (n + 1) for _ in range(n + 1)] # 개선 (maxsize to 0)

for _ in range(k):
    a, b = map(int, ip().split()) # 개선
    arr[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 arr[i][k] + arr[k][j] == 2:
                arr[i][j] = 1


s = int(input())
for _ in range(s):
    x, y = map(int, ip().split()) # 개선
    if arr[x][y] == 1:
        print(-1)
    elif arr[y][x] == 1:
        print(1)
    else:
        print(0)