백준 2618번: 경찰차 (Dynamic Programming)

문제링크:2618번: 경찰차 (acmicpc.net)

2618번: 경찰차

이 문제의 조건은 먼저 경찰차가 두대 있는데 초기에 한대는 (1,1) 다른 한대는 (N,N) 좌표에 위치한다. 앞으로 W개의 사건들이 벌어지는데, 각 사건마다 사건의 좌표(X,Y) 가 주어진다. 경찰차 한대가 사건을 처리하러 가야 하고, 출동한 경찰차는 그 다음 사건까지 그 사건의 위치에서 대기한다. 여기서 경찰차가 움직인 거리는 만약 (1,1)의 경찰차가 간다면 |X-1|+|Y-1| 으로 맨해튼 거리로 계산하도록 할 때, W개의 사건에서 각각 어떤 경찰차가 움직여야 총 움직인 거리의 합이 최소가 될지를 구하는 문제이다.

 

이 문제는 DP를 사용해서 풀었다. 처음엔 각 케이스당, 경찰차 1의 위치, 경찰차 2의 위치 이렇게 구분해서 DP[케이스][경찰차1][경찰차2] 이렇게 풀려고 했지만 케이스가 1000개이고, 경찰차 위치는 1000*1000이므로 만약 이렇게 푼다면 1000*(1000*1000)^2 로 메모리 초과가 확실할 것이다. 생각해 보니 경찰차의 위치는 초기를 제외하면 무조건 케이스로 표현 할 수 있기에 DP[경찰차1케이스][경찰차2케이스]로 나눈다면 1000*1000으로 메모리 내로 만들 수 있다고 생각했다.

 

틀린풀이) DFS bottom-up

처음엔 DFS를 이용한 bottom up 방식을 사용했다. DP[a][b]에서 a는 경찰차1의 마지막 사건, b는 경찰차 2의 마지막 사건이다. DP[a][b]는 해당 사건 상태까지의 거리 합의 최소값이다. DP[0][0]은 초기 상태로 0이고, case1 진행시 DP[1][0] 또는 DP[0][1]로 진행된다. DP[1][0]은 경찰차 1이 case1을 처리한 경우의 거리 합이다. 다음 케이스 2 진행시 DP[1][0]은 DP[2][0], DP[1][2] 두개로 뻗을 수 있다. 두번째 사건을 경찰차 1이 처리하면 DP[2][0], 2가 처리하면 DP[1][2] 가 될 것이다.

 

이런 방식으로 합을 누적하여 DP를 끝까지 진행하면 DP[W][..] 또는 DP[..][W]에는 마지막 케이스가 진행됐을 때의 최소 거리 합이 저장 될 것이다. 나는 이렇게 DFS로 2가지 경우의 수를  조사하며 만약 탐색한 두개의 가지가 DP[a][b]보다 작은 값이 아니라면 (DP[a][b]를 갱신하지 못한다면), DFS를 실행하지 않는 방법으로 메모이제이션을 했지만 시간 초과를 받았다.

 

예시로 DP[3][2]상태라면 처음으로 DP[1][2]->DP[3][2]로 진행됐다 치면, 당시의 DFS값이 확실한 최소라면 그 후의  DP[0][2]->DP[3][2]는 기존 DP[3][2]보다 크기 때문에 DFS를 중단하여 메모이제이션이 되지만, 만약 최악의 경우 DP[3][2]에 도달한 DFS값들이 순차적으로 작아지게 도달한다면 메모이제이션이 전혀 작동하지 않을 것이다. 시간 초과를 받고 그래서 다음은 BFS를 이용하여, DP를 채워가며 DP[3][2]에서의 탐색을 한번만 진행 할 수 있도록, case가 3까지 진행된 모든 경우를 탐색하고, DP에 저장된 최소값들을 바탕으로 case4에대한 탐색을 진행되는 방식으로 진행했다.

 

틀린풀이2)BFS bottom-up

위에 설명한 것처럼 케이스 별로 먼저 DP를 모두 채운다.

case1 인 경우 DP[0][1], DP[1][0],

case2 인경우 DP[0][2], DP[2][1], DP[2][0], DP[1][2]

case3 인경우 DP[3][2], DP[0][3], ..

이렇게 채워가며 만약 중복이 있더라도 처음으로 탐색한 경우에만 que(덱)에 넣어 주어 한번만 탐색하도록 한다. 이는 탐색하는 DP[a][b]가 INF=(99999999) 이면 처음으로 탐색한 것으로 판단 할 수 있다. 만약 처음으로 탐색한 경우가 아니라면 새로 탐색하는 값이 DP[a][b]의 기존 값보다 작다면 업데이트만 해준다. 이 방식을 사용하면 확실히 각 상태에서의 불필요한 탐색을 지워 메모이제이션 할 수 있지만 문제는 많은 상태들을 que에 저장해줘야 하기 떄문에 메모리 초과를 받았다.

 

맞는풀이) DFS top-down

개인적으로 초기 상태부터 끝까지 채워나가는 bottom up 방식이 더 익숙하고 생각하는걸 구현하기 쉬운 것 같아 최대한 bottom up으로 해보려 했지만 모두 실패해서 top-down방식으로 풀어내 성공했다.

import sys

sys.setrecursionlimit(999999)

N=int(sys.stdin.readline().rstrip())
W=int(sys.stdin.readline().rstrip())

DP=[[99999999 for _ in range(W)] for _ in range(W)]

caserc=[[1,1]] #case별 위치 caserc[0]=경찰차1 초기,caserc[W+1]=경찰차2 초기
for i in range(W):
    caserc.append(list(map(int,sys.stdin.readline().rstrip().split())))
caserc.append([N,N])

def dfs(a,b):
    case=max(a,b)
    posa=a
    if b==0:
        posb=W+1
    else:
        posb=b
        
    if case==W-1:
        move1=abs(caserc[W][0]-caserc[posa][0])+abs(caserc[W][1]-caserc[posa][1])
        move2=abs(caserc[W][0]-caserc[posb][0])+abs(caserc[W][1]-caserc[posb][1])
        DP[a][b]=min(move1,move2)
        return DP[a][b]

    if DP[a][b]!=99999999:
        return DP[a][b]

    move1=abs(caserc[case+1][0]-caserc[posa][0])+abs(caserc[case+1][1]-caserc[posa][1])+dfs(case+1,b)
    move2=abs(caserc[case+1][0]-caserc[posb][0])+abs(caserc[case+1][1]-caserc[posb][1])+dfs(a,case+1)
    DP[a][b]=min(move1,move2)
    return DP[a][b]

mindis=(dfs(0,0))

print(mindis)

def find_path(a,b):

    case=max(a,b)
    posa=a
    if b==0:
        posb=W+1
    else:
        posb=b
        
    if case==W-1:
        move1=abs(caserc[case+1][0]-caserc[posa][0])+abs(caserc[case+1][1]-caserc[posa][1])
        move2=abs(caserc[case+1][0]-caserc[posb][0])+abs(caserc[case+1][1]-caserc[posb][1])
        if move1<move2:
            print('1')
        else:
            print('2')
        return
    
    move1=DP[case+1][b]+abs(caserc[case+1][0]-caserc[posa][0])+abs(caserc[case+1][1]-caserc[posa][1])
    move2=DP[a][case+1]+abs(caserc[case+1][0]-caserc[posb][0])+abs(caserc[case+1][1]-caserc[posb][1])
    if move1<move2:
        print('1')
        find_path(case+1,b)
    else:
        print('2')
        find_path(a,case+1)

find_path(0,0)

caserc는 각 case당 위치 좌표를 저장하고 있다. dfs과정에서 b가 0일때 경찰차 2의 초기 상태이므로 caserc[W+1]에 담겨있기에 그때만 posb를 W+1로 바꾸어 주었다. 만약 W-1일때, 마지막 케이스 탐색이므로 경찰차 1이 간 경우 move1, 2가 간 경우 중 move2 더 작은 값을 DP에 저장하고 반환한다. 케이스가 W-1전이라면 DFS를 통해 move1, move2를 구해주고 구했을 시 더 작은 값을 DP에 저장한다. 메모이제이션은 DP[a][b]가 top-down 방식으로 갱신되어 항상 최소로 갱신되므로 만약 DP[a][b]가 갱신되었다면 (INF가 아니라면) DFS탐색과 move1 move2 비교를 통해 구하는 과정을 하지 않고 바로 DP[a][b]를 반환한다.

 

다음 문제는 문제는 최소값 뿐만 아니라 그 방법도 요구하기에 find_path()함수를 통해 최소가 되는 경로를 탐색하며 출력해주었다. a,b 상태에서 move1는 이후 최소 거리가 DP[case+1][b]+현재 a위치에서 case+1까지의 거리 가 될 것이고, move2는 이후 최소 거리가 DP[a][case+1]+현재b위치에서case+1까지의 거리 일 것이다. 둘 중 작은 것이 최소값으로의 경로이기 떄문에 최소값이 나오는 곳으로 DFS를 뻗어가며 출력해준다.

 

처음엔 쉬워 보이는 문제였지만 메모리, 시간 최적화 시키는 것이 어려웠던 문제이다. BFS가 확실히 DFS보다 최단 거리 탐색 등과 같은 문제에는 쉽지만, 메모리를 많이 먹는다는 장단점을 보여주고 DFS는 메모리에선 우세하지만 가지치기와 메모이제이션을 잘 해야 한다는 장단점을 보여주는 문제였다. 공들여서 틀린 풀이를 두번이나 만들어서 초반 계획 수립의 중요성도 알려주는 문제였다.