[BOJ] - python 경찰차 (빡구현 + dp + dfs)

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

2618번: 경찰차

오늘은 그냥 스프란드-그런디 게임이론중에 대표문제인 님게임 시리즈를 둘러보더가, 좀 재밌는 dp문제 없나 싶어서 인터넷을 보다가 KOI 중등 2번을 발견하고 바로 풀게 되었습니다. 예전에는 KOI 초등부 문제에도 벽을 느껴서 잘 풀지 못하는 나였는데, 벌써 중등부 문제를 차근차근 풀고 있다니 너무 대견했다.

문제를 처음 보니, 빡구현 + dfs + dp문제 같았습니다. 전형적으로 코드의 길이가 무자비하게 길어질거 같았고, 은근 생각해야 할 부분이 있을거 같았습니다. 이 문제에는 사건이 들어온 순서를 경찰차 1, 2가 순서대로 거리의 합이 최소가 되도록 처리해 주어야 합니다. 이 부분에서 dfs인 것을 알 수 있었고, 완전 탐색 하기에는 $O(2^N)$이라 TLE가 날게 뻔했기 때문에 dp를 통해 최적화 까지 해주어야 함을 단번에 알 수 있었습니다.

 

그리고 각각의 사건을 1, 2, 3, 4,... W이라고 할 때, 이 사건마다 경찰차1, 2번을 배분하는 걸 dfs로 구현해야 겠다고 생각했습니다. 그리고 dp배열을 $dp[i][j] = police1, police2각각 i, j번 사건을 완료했을 때 까지의 거리의 최소비용$이라고 정의하고 시작했습니다. 또한 마지막에 $dp[0][0]$을 출력을 하면 끝인 것이 아니였습니다. 백트레킹?을 통해 Route또한 계산해 내어야 했습니다. 이를 위해 route라는 함수를 만들었고, LCS에서 백트레킹 했을때와 비스무리하게 진행했더니, TC는 통과하길래 제출했더니 바로 AC처리 되었습니다.

 

import sys
input = sys.stdin.readline
answer = 0

n = int(input())
w = int(input())

incident = [(-1, -1)] # <- dummy incident 1부터 시작해주기 위함
city = [[0] * (n + 2) for _ in range(n + 2)]
police = [(1, 1), (n, n)] # 경찰차의 번호를 저장할 배열
dp = [[-1] * (w + 2) for _ in range(w + 2)]

for idx in range(1, w+1):
    incident.append(tuple(map(int, input().split())))
'''
    police1, police2가 현재 상태에 있을 떄, 다음 사건으로의 거리를 계산해 준다.
    
'''
def calc_dist(police1, police2):
    '''
        police의 위치가 처음 위치라면 따로 처리해주어야 한다.
    '''
    if police1 == 0: p1_pos = (1, 1)
    else: p1_pos = incident[police1]
    
    if police2 == 0: p2_pos = (n, n)
    else: p2_pos = incident[police2]
    
    '''
        다음 사건의 인덱스 정보와 위치를 가져온다.
    '''
    n_incident = max(police1, police2) + 1
    n_pos = incident[n_incident]

    '''
        (police1, police2) 각각으로부터의 n_pos까지의 거리를 계산해서 반환한다.
    '''
    return (abs((n_pos[0] - p1_pos[0])) + abs((n_pos[1] - p1_pos[1])),\
        abs((n_pos[0] - p2_pos[0])) + abs((n_pos[1] - p2_pos[1])))
    
'''
    dfs(police1, police2)는
    현재 police1, police2가 맡은 사건의 인덱스가 들어간다. -> 사건은 1부터 시작 ~ W까지
    
    dfs(0, 0) -> dfs(1, 0)
'''
def dfs(police1, police2):
    if dp[police1][police2] != -1:
        return dp[police1][police2]
        
    '''
        종료조건은 모든 사건을 처리했을 떄 n_incident = w + 1일 때라고 할 수 있다.
    '''
    n_incident = max(police1, police2) + 1
    if n_incident >= w + 1:
        return 0
    
    '''
        현재 상태에서 police1또는 police2가 다음 사건을 맡아야 한다.
        완전 탐색(dfs) + 동적계획법(dp)를 통해 문제를 해결해야 한다.
        
        police1이 다음 사건을 맡는 경우와 police2가 다음 사건을 맡는 경우를 모두 계산해준다.
    '''
    calc_pos = calc_dist(police1, police2)
    
    p1_dist = calc_pos[0] + dfs(n_incident, police2)
    p2_dist = calc_pos[1] + dfs(police1, n_incident)
    
    dp[police1][police2] = min(p1_dist, p2_dist)
    return dp[police1][police2]
        
'''
    dp[0][0]
    
    dp[0][1] -> police1이 0번, police2가 1번을 끝냈을떄의 
    dp[1][0] -> police1이 1번, police2가 0번을 끝냈을 때
    
    이 둘 중에 calc_pos를 police1, police2를 해서 나오는 것과 더해서 더 작은 것을 출력해 나가야 한다.
'''
def route(police1, police2):
    n_pos = max(police1, police2) + 1
    if n_pos >= w + 1:
        return
    
    calc_pos = calc_dist(police1, police2)
    
    cp1 = calc_pos[0] + dp[n_pos][police2]
    cp2 = calc_pos[1] + dp[police1][n_pos]
    if cp1 < cp2:
        print(1)    
        route(n_pos, police2)
    else:
        print(2)
        route(police1, n_pos)
    
    
dfs(0, 0)
print(dp[0][0])
route(0, 0)

코드가 길지만 그닥 어렵지는 않은 문제였습니다. 총 시간 복잡도 $O(N^2)$로 해결할 수 있었습니다.