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]을 출력하고, 경로를 추적하여 출력한다.
오늘의 교훈) 이전에 풀지 못하고 넘겼던 문제들을 해결해보자