BaekJoon 2618번 : 경찰차 (python)

BaekJoon 2618번 : 경찰차 (P4 34.802%)

경찰차 문제

DP 역추적 문제중에 가장 어려웠던 문제인 것 같다.
사실은 아직도 완벽히 이해했다고 보기 어려운 문제인 것 같다.

• 이번 문제에서 dp를 어떻게 설정할 것이냐부터 고비가 있었다. 사실 dp[i][j]라 하였을 때 i를 1번 경찰차의 마지막 사건, j를 2번 경찰차의 마지막 사건이라 가정하는 부분이 가장 어려운 것 같다.
• 'solve'함수는 두 경찰차가 사건을 처리할 때 발생하는 최소 이동 거리를 계산한다. 재귀를 호출하는 부분에서 a_dist는 경찰차 1이 'next'사건을 처리할 때의 총 이동거리를 의미하게 되고 이 값을 통해 현재 위치에서 경찰차1을 움직이는 것이 효율적일지 경찰차2를 움직이는것이 효율적인지를 체크할 수 있게 되는 것이다.
• 그렇게 두 경찰차 중 'next'사건을 처리하는 이동거리가 짧은 값을 'dp[a][b]'에 저장하게 된다. 즉 미래에 더 짧게 갈 수 있는 경찰차를 움직인다는 것을 의미하게된다.
• 마지막 역추적 부분에서 a와 b를 처음에 있던 위치 0과 1에서부터 시작하여 W의 크기만큼 반복문을 돌리게 된다. 이 부분에서 trace[a][b]는 현재의 사건을 해결한 경찰차의 정보 1 or 2를 담고 있게 되고 trace의 a,b 사건정보를 업데이트하면서 현재 사건을 어떤 경찰차가 해결했는지를 출력하게 된다.

느낀점

다른 분들의 풀이를 봐도 이해하기 힘든 문제였던 것 같다...
재귀의 부분과 DP점화식을 떠올리는 부분에서 아직은 많이 부족하다는 것을 느끼게 된 문제였다.
이번 풀이에서는 기본적으로 Top-Down방식의 재귀DP를 이용해서 풀게 되었지만 아마 recursive의 한계가 있는 문제로 변형이 된다면 풀리지 않을 것 같아서 Bottom-Up방식의 DP풀이법도 어렵지만 찾아보며 공부해야겠다는 생각이 든다.

import sys
input = sys.stdin.readline

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

def solve(a,b) :
    next = max(a,b) + 1

    if next == W+2 :
        return 0
    if dp[a][b] != -1 :
        return dp[a][b]
    
    a_dist = solve(next,b) + dist(a, next)
    b_dist = solve(a,next) + dist(b, next)

    if a_dist < b_dist :
        dp[a][b] = a_dist
        trace[a][b] = 1
    else :
        dp[a][b] = b_dist
        trace[a][b] = 2
    
    return dp[a][b]

N = int(input())
W = int(input())
incidnet = [[1,1],[N,N]]

for _ in range(W) :
    i, j = map(int,input().split())
    incidnet.append([i,j])

dp = [[-1]*1002 for _ in range(1002)]
trace = [[-1]*1002 for _ in range(1002)]
print(solve(0,1))

a, b = 0, 1
for i in range(2, W+2) :
    print(trace[a][b])
    if trace[a][b] == 1 :
        a = i
    else :
        b = i