[BOJ] Q2618 경찰차

[BOJ] Q2618 경찰차

Question

Language: Python

Difficulty: Gold 1~2

해당 문제는 Q2666문제와 유사하다.

이동거리의 합이 최소

다만, 해당 문제는 행/열이 큰 형태의 이차원 배열이기 때문에 모든 좌표에 대해 dp를 유지하려고 하면 메모리 초과가 발생하게 된다.

그래서, 경찰차 좌표를 어떻게 보관할지에 대한 부분을 생각해내기 까다롭다, 문제를 자세히 보면 경찰차가 이동할 수 있는 좌표는 사건이 발생하는 좌표로 한정적이다. 따라서, 사건을 저장하고 있는 좌표를 활용해서 경찰차의 좌표를 표현할 수 있다. 그렇게 되면 경찰차의 좌표는 index로 표현하는 것이 가능하다.

아래와 같이 각각의 경찰차에 대한 좌표를 보관한다.

n_locations=int(input())
for _ in range(n_locations):
    row,col=map(int,input().split())
    locations.append((row-1,col-1))

police1=[[0,0]] + locations
police2=[[N-1,N-1]]+ locations

그외의 부분은 dfs+dp를 활용하는 방식이다.

경로를 추적하는 함수

위의 함수를 통해 dp를 만들게 되면 경로를 추적하는 부분은 매우 간단해진다.

처음부터 각각의 사건을 처리하면서, dp를 통해 남는 거리를 파악 가능하기 때문에, 남는 거리가 짧은 쪽으로 경로를 따라가면서 경찰차 번호를 출력하면 된다.

Solution

from math import inf
import sys
def solution(index,police1_index,police2_index):
    global dp,path
    
    if index == (n_locations+1):
        return 0

    if dp[police1_index][police2_index] != -1:
        return dp[police1_index][police2_index]

    next_val=locations[index-1]

    distance1=abs(next_val[0]-police1[police1_index][0])+abs(next_val[1]-police1[police1_index][1])+solution(index+1,index,police2_index)
    distance2=abs(next_val[0]-police2[police2_index][0])+abs(next_val[1]-police2[police2_index][1])+solution(index+1,police1_index,index)

    if distance1 < distance2:
        dp[police1_index][police2_index]=distance1
        return distance1
    else:
        dp[police1_index][police2_index]=distance2
        return distance2

def track_path(index,police1_index,police2_index):    
    if index == (n_locations+1):
        return 0

    next_val=locations[index-1]

    distance1=abs(next_val[0]-police1[police1_index][0])+abs(next_val[1]-police1[police1_index][1]) + dp[index][police2_index]
    distance2=abs(next_val[0]-police2[police2_index][0])+abs(next_val[1]-police2[police2_index][1]) + dp[police1_index][index]

    if distance1 < distance2:
        print(1)
        track_path(index+1,index,police2_index)
    else:
        print(2)
        track_path(index+1,police1_index,index)



if __name__ == "__main__":
    sys.setrecursionlimit(10**5)
    locations=[]
    N=int(input())
    n_locations=int(input())

    for _ in range(n_locations):
        row,col=map(int,input().split())
        locations.append((row-1,col-1))

    police1=[[0,0]] + locations
    police2=[[N-1,N-1]]+ locations

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

    print(solution(1,0,0))
    track_path(1,0,0)