2618- 백준 - 경찰차

1. 문제 출처

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

2618번: 경찰차

2. 풀이

자세한 풀이는 내일

import sys
sys.setrecursionlimit(10**6)

N = int(input())

W = int(input())

distance_list = [[-1 for _ in range(W)] for _ in range(W)]
r = []
def min_distance(cop1,cop2):
    if (cop1 ==(W)) | (cop2==(W)): return 0
    if distance_list[cop1][cop2] !=-1 :return distance_list[cop1][cop2]
    
    case_num = max(cop1,cop2)+1

    cop1_dist = get_distance([1,1],case_list[case_num])\
    if cop1 == 0 else\
    get_distance(case_list[cop1],case_list[case_num])
    
    cop2_dist = get_distance([N,N],case_list[case_num])\
    if cop2 == 0 else\
    get_distance(case_list[cop2],case_list[case_num])
    
    results1 = cop1_dist+min_distance(case_num, cop2)
    results2 = cop2_dist+min_distance(cop1, case_num)
    distance_list[cop1][cop2] = min(results1,results2)
    return distance_list[cop1][cop2]

def route(cop1 , cop2):
    if (cop1 ==W) | (cop2==W): return
    
    case_num = max(cop1,cop2)+1

    cop1_dist = get_distance([1,1],case_list[case_num])\
    if cop1 == 0 else\
    get_distance(case_list[cop1],case_list[case_num])
    
    cop2_dist = get_distance([N,N],case_list[case_num])\
    if cop2 == 0 else\
    get_distance(case_list[cop2],case_list[case_num])
    
    results1 = cop1_dist+min_distance(case_num, cop2)
    results2 = cop2_dist+min_distance(cop1, case_num)
    if results1 < results2:
        r.append(1)
        route(case_num,cop2)
    else:
        r.append(2)
        route(cop1, case_num)


def get_distance(x,y):
    return abs(x[0] - y[0])  + abs(x[1]-y[1])

case_list = [-1 for _ in range(W+1)]
for idx in range(1,W+1):
    case_list[idx] = (list(map(int,input().split())))

print(min_distance(0,0))
route(0,0)
for i in r:
    print(i)