📕문제

[Baekjoon] 12908. 텔레포트 3

문제 설명

크기가 무한인 격자판이 존재할 때 시작점인 (xs, ys)에서부터 도착점인 (xe, ye)까지 가는 데 걸리는 최소 시간을 구하는 문제다.
기본적으로 상하좌우로 한 칸씩 이동하는 데 1초씩 걸린다.
추가로 두 구간((x1, y1), (x2, y2))을 10초만에 이동할 수 있는 텔레포트가 총 3개 존재한다.

---

📝풀이

import sys
read = sys.stdin.readline

points = [tuple(map(int, input().split())) for _ in range(5)]
points = [points[0], points[1], points[2][:2], points[2][2:],
          points[3][:2], points[3][2:], points[4][:2], points[4][2:]]

INF = sys.maxsize
n = len(points)
graph = [[INF] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if i == j:
            graph[i][j] = 0
        else:
            graph[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])

for i in range(2, n, 2):
    graph[i][i + 1] = graph[i + 1][i] = 10

for k in range(8):
    for i in range(8):
        for j in range(8):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

print(graph[0][1])

• 각 점을 튜플 형식으로 저장.
• 각 구간별 길이를 INF로 설정하고
  자기 자신까지의 거리는 0, 각 구간까지의 거리를 계산해 저장.
• 텔레포트 구간끼리의 거리는 10으로 설정.
• 플로이드 워셜 알고리즘을 통해 모든 점 간 최소 거리를 계산.
• 시작점부터 도착점까지의 거리 출력.