백준 2618번: 경찰차 [python]

난이도 : 플래티넘 4
유형 : DP (동적계획법)
https://www.acmicpc.net/problem/2618

문제

가로, 세로가 N인 도로 위에서 두 대의 경찰차가 각각 사건을 처리한다.
총 W번의 사건이 주어지며, 각 사건마다 (x,y) 좌표가 주어진다.

• 경찰차 1번은 (1,1)에서 출발.
• 경찰차 2번은 (N,N)에서 출발.
• 두 경찰차는 각 사건을 나누어 처리할 수 있다.
• 이동 거리의 합을 최소로 하도록 사건을 배분해야 한다.

출력
1. 모든 사건을 처리할 때 이동 거리의 합의 최솟값
2. 각 사건을 누가 담당했는지(1번 or 2번)를 사건 순서대로 출력

문제 접근

• 사건의 순서를 바꾸면 안 됨 → W번의 사건을 앞에서부터 하나씩 배정해야 함.
• 현재 시점에서 1번 경찰차가 마지막으로 처리한 사건 번호, 2번 경찰차가 마지막으로 처리한 사건 번호만 알면 이후 상태를 결정할 수 있음.
• 따라서 DP로 상태를 정의:
  • dp[a][b] = a번 사건을 1번차가 마지막으로 처리, b번 사건을 2번차가 마지막으로 처리했을 때의 최소 이동거리
  • 항상 max(a,b)+1번째 사건을 처리해야 한다.

핵심 아이디어

• 재귀 + 메모이제이션으로 solve(a,b) 구현
• 다음 사건 번호 next = max(a,b)+1
• 두 선택지 중 최소를 선택:
  • next 사건을 1번차가 처리하는 경우
  • next 사건을 2번차가 처리하는 경우
• 거리 계산: 두 점 사이의 맨해튼 거리 |x1-x2| + |y1-y2|
• 시작점 처리:
  • 사건 0번의 좌표는 경찰차의 시작 위치로 가정
    • car1: (1,1)
    • car2: (N,N)

해답 및 풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
W = int(input())
events = [(0,0)]  # 인덱스 맞추기용 (0번은 안씀)
for _ in range(W):
    x, y = map(int,input().split())
    events.append((x,y))

# 시작 위치를 사건 0번으로 간주
car1_start = (1,1)
car2_start = (N,N)
events[0] = car1_start  # 1번차 시작점
# car2는 별도로 관리

# 메모이제이션
dp = [[-1]*(W+1) for _ in range(W+1)]
choice = [[0]*(W+1) for _ in range(W+1)]

def dist(a,b):
    return abs(events[a][0]-events[b][0]) + abs(events[a][1]-events[b][1])

def solve(a,b):
    if a == W or b == W:  # 모든 사건 처리 완료
        return 0
    if dp[a][b] != -1:
        return dp[a][b]

    next_event = max(a,b)+1
    # 1번차가 처리
    cost1 = solve(next_event,b) + dist(a,next_event)
    # 2번차가 처리
    # 2번차는 시작위치가 (N,N)이므로 별도 처리
    if b == 0:
        cost2 = solve(a,next_event) + (abs(events[next_event][0]-car2_start[0]) + abs(events[next_event][1]-car2_start[1]))
    else:
        cost2 = solve(a,next_event) + dist(b,next_event)

    if cost1 < cost2:
        dp[a][b] = cost1
        choice[a][b] = 1
    else:
        dp[a][b] = cost2
        choice[a][b] = 2

    return dp[a][b]

# 최솟값 구하기
answer = solve(0,0)
print(answer)

# 경로 추적
a, b = 0, 0
for _ in range(W):
    if choice[a][b] == 1:
        print(1)
        a = max(a,b)+1
    else:
        print(2)
        b = max(a,b)+1