[백준] 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())
느낀 점
변하는 값이 너무 많아 처음에는 접근이 어려웠지만, 천천히 안 변하는 값을 중심으로 생각하니 점화식을 발견할 수 있었다. 다른 풀이에 의존하지 않고 스스로 풀어서 너무 기분이 좋았던 문제다.