[BOJ 16958 🥇4] 텔레포트 (Python)

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

16958번: 텔레포트

 

문제

2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다.

두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자.

입력

첫째 줄에 도시의 수 N, 텔레포트하는데 걸리는 시간 T가 주어진다.

둘째 줄부터 N개의 줄에 도시의 정보를 의미하는 세 정수 s, x, y가 1번 도시부터 N번 도시까지 순서대로 주어진다. s가 1인 경우에는 특별한 도시라는 의미이고, 0인 경우는 특별한 도시가 아니라는 의미이다. (x, y)는 도시의 좌표이다.

다음 줄에는 M이 주어지고, 다음 M개의 줄에는 두 도시 A와 B가 주어진다. 

출력

총 M개의 줄에 걸쳐서 A에서 B에 가는 최소 이동 시간을 출력한다.

제한

• 2 ≤ N ≤ 1,000
• 1 ≤ T ≤ 2,000
• 1 ≤ M ≤ 1,000
• 0 ≤ x, y ≤ 1,000
• A ≠ B
• 두 도시의 좌표가 같은 경우는 없다.

 

예제 입력 1

6 3
0 1 2
0 5 1
1 3 3
1 1 5
0 3 5
1 7 5
5
1 2
1 5
1 6
3 4
4 2

 

예제 출력 1 

5
5
6
3
7

 

예제 입력 2 

6 2
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
6
1 2
2 3
3 4
4 5
5 6
6 1

 

예제 출력 2 

1
1
2
1
1
2

⭕ CODE

import sys

sys.stdin = open('input.txt')

from pprint import pprint

input = sys.stdin.readline

n, t = map(int, input().split())

inf = int(1e9)

arr = [[inf] * (n + 1) for _ in range(n + 1)]

city = [0]
for _ in range(n):
    # s : 1 -> 특별한 도시 텔레포트 가능 0 -> 불가능
    # x,y 도시 좌표
    s, x, y = map(int, input().split())
    city.append((s, x, y))

# 텔레포트 불가능한 지점에서 가장 가까운 텔레포트 지점까지의 거리를 저장하기 위한 near
near = [0] * (n + 1)
for i in range(1, n + 1):
    # 이 도시가 텔포 불가능한 지점이라면
    # 가장 가까운 텔포지점을 찾자
    if city[i][0] == 0:
        # 최소거리를 구하기 위한 minvalue
        minvalue = inf
        for j in range(1, n + 1):
            # 텔레포트 가능한 지점이고 거리가 가장 가까운거를 찾기
            if city[j][0] == 1 and abs(city[i][1] - city[j][1]) + abs(city[i][2] - city[j][2]) < minvalue:
                minvalue = abs(city[i][1] - city[j][1]) + abs(city[i][2] - city[j][2])
                near[i] = minvalue

# 경우의 수 4가지

# 둘다 텔포 불가능
# -> 직선거리와
# 시작점에서 가장 가까운 텔포지점이동후 텔포
# 도착점에서 가장 가까운 텔포지점 이동후 도착지까지 움직이기 와 비교하기

# 둘다 텔포 가능
# -> 직선거리와
# -> 텔포 타는데 걸리는 시간 비교

# 시작점만 텔포 가능
# -> 도착점에서 가장 가까운 텔포지점으로 텔포타자 그리고 그냥 직선 거리와 비교하자

# 도착점만 텔포 가능
# -> 시작점에서 가장 가까운 텔포지점으로 텔포타자 그리고 그냥 직선 거리와 비교하자

for i in range(1, n + 1):
    for j in range(1, n + 1):
        s1, x1, y1 = city[i]
        s2, x2, y2 = city[j]

        # 출발지점과 도착지점이 같으면 0
        if i == j:
            arr[i][j] = 0

        # 출발지 도착지가 다른경우
        else:
            # 둘다 텔포 불가능한 경우는
            if s1 == 0 and s2 == 0:
                # 직선거리와
                # 시작지점에서 가장 가까운 텔포지점거리 near[i]와
                # 도착지점에서 가장 가까운 텔포지점거리 near[j]와
                # 텔포하는데 걸리는 시간 t를 더한거를 비교
                arr[i][j] = min(abs(x1 - x2) + abs(y1 - y2), near[i] + near[j] + t)
            # 도착지점만 텔포가능한 경우는
            elif s1 == 0 and s2 == 1:
                # 직선거리와
                # 도착지점에서 가장 가까운 텔포지점거리 near[j]와
                # 텔포하는데 걸리는 시간 t를 더한거를 비교
                arr[i][j] = min(abs(x1 - x2) + abs(y1 - y2), near[i] + t)
            # 시작지점만 텔포가능한 경우는
            elif s1 == 1 and s2 == 0:
                # 직선거리와
                # 시작지점에서 가장 가까운 텔포지점거리 near[i]와
                # 텔포하는데 걸리는 시간 t를 더한거를 비교
                arr[i][j] = min(abs(x1 - x2) + abs(y1 - y2), near[j] + t)
            # 둘다 텔포 가능한 경우는
            elif s1 == 1 and s2 == 1:
                # 직선거리와
                # 텔포하는데 걸리는 시간 t 비교
                arr[i][j] = min(abs(x1 - x2) + abs(y1 - y2), t)

m = int(input())

for _ in range(m):
    a, b = map(int, input().split())

    print(arr[a][b])

✏️ Comment

이동하는 경우가 4가지 있다고 생각하고 구현으로 풀었다.

문제의 조건 중에서 둘다 텔포 불가능한 경우에 텔레포트를 한번 타야하는데 두번탄다고 생각하여 걸리는 시간을 2*t를 곱해주어서 틀렸었다. 문제 조건을 잘 읽자

 

• 문제 조건을 잘 읽자