[Python/BOJ] 12908. 텔레포트 3

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

12908번: 텔레포트 3

문제

수빈이는 크기가 무한대인 격자판 위에 살고 있다. 격자판의 각 점은 두 정수의 쌍 (x, y)로 나타낼 수 있다.

제일 처음에 수빈이의 위치는 (xs, ys)이고, 집이 위치한 (xe, ye)로 이동하려고 한다.

수빈이는 두 가지 방법으로 이동할 수 있다. 첫 번째 방법은 점프를 하는 것이다. 예를 들어 (x, y)에 있는 경우에 (x+1, y), (x-1, y), (x, y+1), (x, y-1)로 이동할 수 있다. 점프는 1초가 걸린다.

두 번째 방법은 텔레포트를 사용하는 것이다. 텔레포트를 할 수 있는 방법은 총 세 가지가 있으며, 미리 정해져 있다. 텔레포트는 네 좌표 (x1, y1), (x2, y2)로 나타낼 수 있으며, (x1, y1)에서 (x2, y2)로 또는 (x2, y2)에서 (x1, y1)로 이동할 수 있다는 것이다. 텔레포트는 10초가 걸린다.

수빈이의 위치와 집의 위치가 주어졌을 때, 집에 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 xs와 ys가, 둘째 줄에 xe, ye가 주어진다. (0 ≤ xs, ys, xe, ye ≤ 1,000,000,000)

셋째 줄부터 세 개의 줄에는 텔레포트의 정보 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000,000)

입력으로 주어지는 모든 좌표 8개는 서로 다르다.

출력

수빈이가 집에 가는 가장 빠른 시간을 출력한다.

풀이

Code

import sys, math
input = sys.stdin.readline
INF = math.inf
xs, ys = map(int, input().split())
xe, ye = map(int, input().split())

# 1. 플로이드-워셜을 위한 graph 생성
graph = [[INF for _ in range(8)] for _ in range(8)]
# 2. 자기 자신에서 자기 자신으로 가는 비용 초기화
for i in range(8) :
    graph[i][i] = 0
# 3. 인덱스 정보 입력용 딕셔너리 생성
# 시작점 인덱스 : 0, 끝점 인덱스 : 7
dic = {}
dic[0], dic[7] = (xs, ys), (xe, ye)
# 4. for문을 통해 간선 정보 입력받기
i = 1
for _ in range(3):
    s1, e1, s2, e2 = map(int, input().split())
    # 딕셔너리에 인덱스 입력
    dic[i], dic[i+1] = (s1, e1), (s2, e2)
    # graph에 점프 이동, 텔레포트 이동 중 작은 값 입력
    jump = abs((s2 - s1)) + abs((e2 - e1))
    graph[i][i+1] = min(10, jump)
    graph[i+1][i] = min(10, jump)
    i+=2

# 5. 텔레포트가 불가능한 지역은 점프로 이동하는 거리 입력
for i in range(8) :
    for j in range(8) :
        if graph[i][j] == INF :
            graph[i][j] = abs(dic[i][0] - dic[j][0]) + abs(dic[i][1] - dic[j][1])

# 6. 플루이드-워셜 알고리즘 수행
graph[0][7], graph[7][0] = abs((xe - xs)) + abs((ye - ys)), abs((xe - xs)) + abs((ye - ys))
for k in range(8) :
    for i in range(8) :
        for j in range(8) :
            if i!=j :
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 7. 결과 출력
print(graph[0][7])