[백준 12908] 텔레포트 3 (Python) / G5

문제

12908. 텔레포트 3

코드

# 12908
def cal_time(dot1, dot2):
    return abs(dot1[0] - dot2[0]) + abs(dot1[1] - dot2[1])

xs, ys = map(int,input().split())
xe, ye = map(int,input().split())

# 시작점, 텔레포트 위치, 끝점 순으로 점 8개가 들어감
dot = [0] * 8
dot[0] = (xs, ys)
dot[7] = (xe, ye)

# distance[0][1] = 0번 점 ~ 1번 점 사이의 거리
distance = [[float('inf')] * 8 for _ in range(8)]
distance[0][7] = distance[7][0] = cal_time(dot[0], dot[7])

for i in range(1,4):
    x1, y1, x2, y2 = map(int,input().split())
    dot[i*2-1] = (x1, y1)
    dot[i*2] = (x2, y2)
    # 순간이동과 점프 중 더 빠른 것 선택
    distance[i*2-1][i*2] = distance[i*2][i*2-1] = min(cal_time(dot[i*2-1], dot[i*2]), 10)

for i in range(8):
    for j in range(8):
        distance[i][j] = min(distance[i][j], cal_time(dot[i], dot[j]))

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


print(distance[0][7])

코드 설명

플로이드 워셜 알고리즘을 사용하였다.
플로이드 워셜은, 우선 각 노드들 간 이어져 있으면 그 거리를 2차원 배열에 적어주고, 연결되어 있지 않으면 무한으로 표기한다.
그 후 노드개수 만큼 순회하며, 각 노드를 거쳐가는 경우를 계산해 2차원 테이블을 갱신시켜 주는 알고리즘이다.

이를 이용하여, 처음 순간이동 위치를 입력 받고, distance에 해당 텔레포드끼리의 점을 점프하는 것과, 텔레포트하는 것 중 시간이 더 짧은 것으로 저장해주고,

각 점의 거리를 계산해서 테이블을 갱신하고,

해당 점을 거쳐가는 경우를 계산해서 테이블을 완성시켜주었다.

플로이드 워셜만 알면 쉽게 해결 가능한 문제였다.