[파이썬/python] 백준 - 2159 케익배달

문제

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

---

문제 설명

1. 보나뻬띠 업체에서 N명의 고객에게 케익을 배달한다.
2. 무조건 입력 받는 고객 순서대로 배달을 진행한다.
   1.  배달을 진행할 때 고객의 인접 격자점으로 이동해도 배달이 가능하다.
   2. 고객의 현 위치 또한 가능하다.
3. 모든 배달을 완료했을 때의 최단거리를 구한다.    

 

---

풀이

고객의 수는 최대 $N = 10^5$이다. 이때 A 고객에서 B 고객으로 이동할 때의 연산 횟수는 5*5이다.

배달에는 순서가 정해져 있기 때문에 한 번의 배달을 할 때마다 25번의 연산이 주어지고, 총 $10^5$의 배달을 진행한다고 가정하면 , $25 * 10^5$의 연산이 나오기 때문에 2초라는 시간제한에 충분히 접근 가능한 풀이이다.

따라서 이전 고객까지의 최단거리를 저장하고 재사용하는 메모리제이션을 통해 최댓값을 계속 갱신했다.

 

1. 시작지점은 다섯방향이 아니므로 업체의 위치 기준 첫 번째 고객까지의 최단거리를 갱신한다.
2. 첫 번째 고객부터 마지막 고객까지 순서대로 5가지 방향의 최단거리를 갱신한다.
3. 마지막 고객의 5가지 방향의 거리 중 최솟값을 출력한다.

---

코드

import sys
input = sys.stdin.readline
#상,하,좌,우
dy = [0,1,0,-1,0]
dx = [1,0,-1,0,0]
N = int(1e5)
INF = sys.maxsize

def cal_dist(y1,x1,y2,x2):
    return abs((y2-y1))+ abs((x2-x1))

n = int(input())
dp = [[INF for _ in range(5)] for _ in range(n+1)]
pos = [list(map(int,input().split())) for _ in range(n+1)]
for i in range(5):
    dp[0][i] = 0

#출발점 초기화
y1,x1 = pos[0][0], pos[0][1]
y2,x2 = pos[1][0], pos[1][1]

for i in range(5):
    ny2 = y2 + dy[i]
    nx2 = x2 + dx[i]

    if ny2 < 0 or ny2 > N-1 or nx2 < 0 or nx2 > N-1:
        continue
    dp[1][i] = cal_dist(y1,x1,ny2,nx2)

for i in range(2,n+1):
    y1,x1 = pos[i-1][0], pos[i-1][1]
    y2,x2 = pos[i][0], pos[i][1] 

    #도착 지점
    for j in range(5):
        ny2 = y2 + dy[j]
        nx2 = x2 + dx[j]

        if ny2 < 0 or ny2 > N-1 or nx2 < 0 or nx2 > N-1:
            continue
        #출발 지점
        for k in range(5):
            ny1 = y1 + dy[k]
            nx1 = x1 + dx[k]

            if ny1 < 0 or ny1 > N-1 or nx1 < 0 or nx1 > N-1:
                continue

            dp[i][j] = min(dp[i][j],dp[i-1][k] + cal_dist(ny1,nx1,ny2,nx2))

print(min(dp[-1]))

 

---

시간복잡도

• 고객의 수 $N = 10^5$, 1번의 배달에 실행되는 연산의 횟수: $5*5 = 25$
• 따라서 약 $O(5*5*10^5) = O(10^6)$의 시간복잡도가 소요된다.