문제 : https://www.acmicpc.net/problem/2618

출처 : https://www.acmicpc.net/problem/2618

문제 설명

두개의 경찰차가 존재하고 순서대로 사건을 부여받는다. 이때 해당 사건의 위치로부터 가까운 경찰차가 담당하고 총 두개의 경찰차가 움직인 거리의 최솟값을 구하면 된다.

풀이

처음에 우선순위 큐를 사용하여 bfs를 시전했다. 그러나 시간초과가 떳고, 다른 방법을 구사해야했다. 저번 글 dance dance revolution 문제와 동일하게 푸는 방식을 선택했고, 역시 dp를 어떻게 구사해야될지 생각했다.
해당 풀이는 다음 글을 참고하여 작성한다.
https://injae-kim.github.io/problem_solving/2020/03/11/baekjoon-2618.html

여기서 생각한 dp는 사건이 순서대로 이루어진다는 점을 사용하여 dp를 다음과 같이 이차원으로 정의했다.
1차원 : car1의 마지막 사건순서
2차원 : car2의 마지막 사건순서
즉, 해당 사건순서(가장 최근)를 어느 경찰차가 담당하느냐를 기준으로 잡는것이다.
예를 들어, dp[1][3]이라면 OABB로 되는 것이다(AABB, BABB 중 min값을 dp[1][3]이 가진다).
이와 같이 dp를 유지하고 이미 연산했다면 return함으로써 같은 연산을 피하는 메모이제이션 방법을 구현하였다.
코드는 다음과 같다

Code

import sys
sys.setrecursionlimit(100000)
# bfs로 하면 시간초과!!

n = int(input())
w = int(input())
cars = [[1,1],[n,n]]
events = []
for _ in range(w):
    a,b = map(int,input().split())
    events.append([a,b])
events = [[0,0]] + events

def calc(a,b):
    y1,x1 = a
    y2,x2 = b
    return abs(y1-y2) + abs(x1-x2)

dp = [[-1] * (w+1) for _ in range(w+1)]



def dfs(car1, car2):
    if car1 == w or car2 == w:
        return 0
    if dp[car1][car2]!=-1:
        return dp[car1][car2]
    next_event = max(car1,car2)+1
    
    if car1==0:
        dist1 = calc([1,1], events[next_event])
    else:
        dist1 = calc(events[car1], events[next_event])
    if car2==0:
        dist2 = calc(events[next_event],[n,n])
    else:
        dist2 = calc(events[next_event], events[car2])
    
    result1 = dist1+dfs(next_event, car2)
    result2 = dist2+dfs(car1, next_event)
    dp[car1][car2] = min(result1, result2)
    return dp[car1][car2]

def dfs2(car1,car2):
    if car1 == w or car2 == w:
        return
    
    next_event = max(car1,car2)+1
    
    if car1==0:
        dist1 = calc([1,1], events[next_event])
    else:
        dist1 = calc(events[car1], events[next_event])
    if car2==0:
        dist2 = calc(events[next_event],[n,n])
    else:
        dist2 = calc(events[next_event], events[car2])
    
    if dist1 + dp[next_event][car2] < dist2 + dp[car1][next_event]:
        print(1)
        dfs2(next_event,car2)
    else:
        print(2)
        dfs2(car1,next_event)
print(dfs(0,0))
dfs2(0,0)

dfs함수는 위에서 설명한 방법으로 구현한 것이고, dfs2는 사건마다 어느 car가 방문했는지 확인하기 위해 dfs함수를 살짝 변형한 것이다. 구한 dp값과 dist를 이용하여 적은 값을 가진 car를 print하는 것이기 때문에 쉽게 이해할 수 있을 것이다.

Result