[백준] 12908 텔레포트 3

문제

• 크기가 무한대인 격자판 위에서 (xs, ys) 위치에서 (xe, ye) 위치로 이동하려고 한다.
• 이동 방법은 두 가지다.
  1) 점프 : (x, y)에 있을 때 상/하/좌/우로 이동한다. (1초 소요)
  2) 텔레포트 : 미리 정해진 위치로의 이동이 가능하다.
  텔레포트는 네 좌표 (x1, y1), (x2, y2)로 나타낼 수 있으며, (x1, y1)에서 (x2, y2)로 또는 (x2, y2)에서 (x1, y1)로 이동할 수 있다. (10초 소요)
• (xe, ye)로 가는 가장 빠른 시간 출력하기

 

• 0 <= xs, ys, xe, ye, x1, y1, x2, y2 <= 1,000,000,000

 

풀이

• 점프로 갈 수 있는 최단 시간은 이미 정해져있다.
• 텔레포트로 시간을 단축할 수 있는지 확인한다.
  -> 텔레포트가 가능한 좌표 별로 최단 거리를 구하기

 

from collections import deque

xs, ys = map(int, input().split())  # 시작위치
xe, ye = map(int, input().split())  # 도착위치
teleport = [(xs, ys), (xe, ye)]     # 텔레포트 좌표들
distance = [[1e10]*(8) for _ in range(8)]	# 각 좌표별 최단거리
for i in range(1, 4) :
    x1, y1, x2, y2 = map(int, input().split())
    teleport.append((x1, y1))
    teleport.append((x2, y2))
    distance[2*i][2*i+1] = 10
    distance[2*i+1][2*i] = 10

for i in range(8) :
    distance[i][i] = 0

# 좌표별로 최단거리 갱신
for i in range(8) :
    for j in range(8) :
        if i == j : continue
        distance[i][j] = min(distance[i][j], abs(teleport[i][0]-teleport[j][0]) + abs(teleport[i][1]-teleport[j][1]))
        distance[j][i] = min(distance[j][i], abs(teleport[i][0]-teleport[j][0]) + abs(teleport[i][1]-teleport[j][1]))

# 플로드워셜
for k in range(8) :
    for i in range(8) :
        for j in range(8) :
            if distance[i][j] > distance[i][k] + distance[k][j] :
                distance[i][j] = distance[i][k] + distance[k][j]

print(distance[0][1])

 

References

• 백준 오늘의 문제