[백준] 2618: 경찰차

 

	1	2	3	4	5	6
1
2			(2, 3)
3					(3, 5)
4
5					(5, 5)
6

문제이해

(1, 1)과 (n, n)에 있는 경찰차 두대가 최소거리로 사건들을 해결하는 방법과 거리를 출력하는 문제이다.

계획

이 문제가 어렵게 느껴지는 이유는 경찰이 현재 있는 위치에 따라 추가되는 거리가 계속해서 달라지기 때문이다. 따라서, 기존의 dp문제처럼 dist[n+1] = dist[n] + min(police1[n], police2[n])와 같은 점화식은 사용할 수 없다.

각 경우에 따라 거리가 달라지기 때문에 모든경우의 수를 탐색하는 방법을 생각할 수 있지만. 사건이 n개일 때의 경우의 수는 2^n개다. 

사건이 3개일때의 경우의 수
111
112
121
122
211
212
221
222

사건의 개수가 1000개까지 있을 수 있으므로 모든 경우의 수는 2^1000라서 절대 모든 경우를 탐색하는 방법은 불가능하다.

하나의 사건을 어떤 경찰이 선택하는지에 중요한것은 각 경찰의 마지막 해결한 사건이다. 그 이전은 어떤 경찰이 어떤 사건을 선택했는지는 별로 중요하지 않다.

	case1	case2	case3	case4	case5	case6
경찰1	어떤 경찰이 사건을 해결하는지 중요하지 않음.			o	o
경찰2			o

만약 경찰2가 case3을 마지막으로 해결하고 경찰 1이 case5를 마지막으로 해결했다면 case6을 경찰 1 이해 결할지 2가 해결할 지결 정하는 것은 case1과 case2가 어떤 경찰이 해결했는지에 영향을 받지 않는다.

따라서 두경찰이 마지막으로 해결한 사건의 경우에 최소거리를 계속해서 저장해 나가다보면 다음과 같은 표를 만들 수 있다.

p1(start, end) = 경찰1이 start에서 end까지 이동한 거리

p2(start, end) = 경찰2이 start에서 end까지 이동한 거리

	경찰1
경 찰 2		0	1	2	3	4	5	6
	0	x	p1(0, 1)	dp[0][1] + p1(1, 2)	dp[0][3] + p1(2, 3)	dp[0][4] + p1(3, 4)	dp[0][5] +  p1(4, 5)	dp[0][6] + p1(5, 6)
	1	p2(0, 1)	x	dp[1][0] + p1(0, 2)	dp[1][3] + p1(2, 3)	dp[1][4] + p1(3, 4)	dp[1][5] +  p1(4, 5)	dp[1][6] + p1(5, 6)
	2		p1(0, 1) + p2(0, 2)	x	min( dp[2][0~1] + p1(0~1, 3) )	dp[2][4] + p1(3, 4)	dp[2][5] +  p1(4, 5)	dp[2][5] +  p1(4, 5)
	3			min( dp[0~1][2] + p2(0~1, 3) )	x	min(dp[2][0~1]) + p1(0~1, 3)
	4				min( dp[0~2][3] + p2(0~2, 4) )	x
	5						x
	6							x

이런식으로 저장된다. 

이런 식으로 탐색한다면 O(N^2) 시간복잡도로 해결할 수 있다.

 

계획수행

import sys

n = int(sys.stdin.readline())
w = int(sys.stdin.readline())
case = [0]+[list(map(int, sys.stdin.readline().split())) for _ in range(w)]
dp = [[int(1e9) for _ in range(w+1)] for _ in range(w+1)]
path = [[0 for _ in range(w+1)] for _ in range(w+1)]
dp[0][0] = 0
dp[1][0] = abs(n-case[1][0]) + abs(n-case[1][1])
dp[0][1] = abs(1-case[1][0]) + abs(1-case[1][1])

def cal_dist(a, b, c):    #거리를 구하는 함수
    if a == 0 and c == 1: a = [1, 1]    
    elif a == 0 and c == 2: a = [n, n]    #만약 a가 0이라면 경찰이 처음 출발하는 거리이다.
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

for i in range(2, w+1):
    for ii in range(i-1):
        dist = dp[i-1][ii] + cal_dist(case[ii], case[i], 1)
        if dp[i-1][i] > dist:
            dp[i-1][i] = dist
            path[i-1][i] = [i-1, ii]        #dp[i-1][i]에 계속해서 최솟값 갱신
        dist = dp[ii][i-1] + cal_dist(case[ii], case[i], 2)
        if dp[i][i-1] > dist:
            dp[i][i-1] = dist
            path[i][i-1] = [ii, i-1]        #dp[i][i-1]에 계속해서 최솟값 갱신
        dp[ii][i] = dp[ii][i-1] + cal_dist(case[i], case[i-1], 1)
        dp[i][ii] = dp[i-1][ii] + cal_dist(case[i], case[i-1], 2)

ans = int(1e9)
lastp = [0, 0]
for i in range(w):
    if ans > dp[i][w]:
        ans = dp[i][w]
        lastp = [i, w]
    if ans > dp[w][i]:
        ans = dp[w][i]
        lastp = [w, i]
#최소거리인 경우 탐색

print(ans)

r, c = lastp[0], lastp[1]
p = []
idx = n
while True:
    if abs(r-c) == 1:
        if r > c:
            p.append(2)
        else:
            p.append(1)
        if path[r][c] == 0:
            break
        r, c = path[r][c][0], path[r][c][1]
    elif r > c:
        r -= 1
        p.append(2)
    else:
        c -= 1
        p.append(1)
#최소거리일 경우의 경로 역추적

while p:
    print(p.pop())

 

느낀 점

변하는 값이 너무 많아 처음에는 접근이 어려웠지만, 천천히 안 변하는 값을 중심으로 생각하니 점화식을 발견할 수 있었다. 다른 풀이에 의존하지 않고 스스로 풀어서 너무 기분이 좋았던 문제다.