[백준 2618번] 경찰차 (Python3)

import sys
input = sys.stdin.readline

def DFS(p1,p2):
  next = max(p1,p2)+1
  if next == W+2:
    return
  if not DP[next][p2]:
    DFS(next,p2)
  if not DP[p1][next]:
    DFS(p1,next)  
  x1,x2 = DP[next][p2]+graph[p1][next],DP[p1][next]+graph[p2][next]
  if x1<x2:
    DP[p1][p2],path[p1][p2] = x1,1
  else:
    DP[p1][p2],path[p1][p2] = x2,2

N,W = int(input()),int(input())

case = [[1,1],[N,N]]+[[*map(int,input().split())] for i in range(W)]
graph = [[0]*(W+2) for i in range(W+2)]
for i in range(W+1):
  for j in range(i+1,W+2):
    graph[i][j] = abs(case[i][0]-case[j][0])+abs(case[i][1]-case[j][1])

DP,path = [[0]*(W+2) for i in range(W+2)],[[0]*(W+2) for i in range(W+2)]
DFS(0,1)
print(DP[0][1])
p1,p2 = 0,1
while max(p1,p2)<W+1:
  print(path[p1][p2])
  if path[p1][p2] == 1:
    p1 = max(p1,p2)+1
  else:
    p2 = max(p1,p2)+1

DFS+DP로 해결하였다.

예전에 이 문제를 처음 봤을때는 풀이가 생각이 안나서 넘어갔던 문제였는데, 오늘 이 문제를 다시 보니 풀이가 한번에 생각났다. DFS+DP 문제를 어느정도 풀다 보니까 이 부분에 있어서는 어느정도 숙달이 된 것 같다.

 

풀이를 설명하면,

1. 모든 사건의 위치와 경찰차의 초기 위치를 저장한 후, 각 위치간의 거리 그래프를 작성한다.

2. DP 배열을 만든다. 이때 DP[p1][p2]는 1번경찰차가 p1, 2번경찰차가 p2에 위치할 때, 남은 사건을 모두 처리하는데 드는 비용이다.

3. path 배열을 만든다. 이때 path[p1][p2]는 1번경찰차가 p1, 2번경찰차가 p2에 위치할 때, 사건을 처리하기 위한 최소비용으로 움직이는 경우 다음 사건을 누가 처리했는지를 기록한다.

4. DFS로 DP[0][1]을 구한다. 이때 DFS를 하면서 경로도 저장해주어야한다.

5. DP[0][1]을 출력하고, 경로를 추적하여 출력한다.

 

 

오늘의 교훈) 이전에 풀지 못하고 넘겼던 문제들을 해결해보자