[백준] 2618 - 경찰차 (Python)

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

 

질문게시판에서 힌트 하나를 얻고 푼 문제..

처음에는 스티커 문제처럼 어떤 사건을 경찰차 1이 해결한 경우, 경찰차 2가 해결한 경우로 나누어서 테이블을 구성하고,

dp[w][1] = 사건 w를 경찰차 1이 해결했을 때, 그때까지 두 경찰차의 최소 이동거리 합 =

min( dp[w-1][1] + dist(w-1, w) , dp[w-1][2] + dist(w-1을 경찰차 2가 해결한 최적해에서의 경찰차 1의 위치, w) )

 

로 두고 dp[w][1], dp[w][2] 로 이루어진 2차원 배열로 풀려고 했다.

 

이렇게 말로만 적어도 벌써부터 점화식이 복잡한데, 이 점화식은 안타깝게도 틀렸다.

비교하고 있는 두 값이 '같은' 경우 어떤 값을 취할 지 정할 수 없기 때문이다.

그리고 이에 대한 반례로 아래와 같은 반레가 있었다.

 

4
5
1 3
2 1
1 3
2 1
1 3

 

 

이 반례를 보고나서 내가 생각한 두번재 흐름은, 최소값으로 가능한 경우가 여러개 있을 때는, 그 모두를 다 저장하고, 그 다음 사건의 최솟값을 구할 때는, 저장한 모든 경우에 대해 각각 새로운 값을 구해서 최소값을 구해야겠다고 생각했다.

 

하지만 이렇게 했을 때도 틀렸다.

그래서 결국 이 문제가 정보 올림피아드 문제인 것을 보고 정올 사이트에서 제출 후, 틀리는 테케를 확인했다.

다행히 사이즈가 작은 테케에서 틀려서 직접 테케를 따라가 볼 수 있었다.

 

테케를 따라가보니 내가 점화식을 생각한 근본 발상 자체가 틀린 발상이었다.

왜냐하면 현재 사건까지 봤을 때 최소값이 부분 최적해라는 보장을 할 수 없기 때문이다.

(정올에서 찾은 반례도 그런 반례였다. 현재 최소값을 저장했는데, 그 값을 얻은 사건 처리 순서가 최적해가 아니었다..)

 

그럼 어떻게 해야할까 고민을 하면서 다시 질문 게시판을 찾아보다가 댓글에서 한가지 힌트를 얻었다.

DP 테이블을 정의할 때, 두 경찰차가 마지막으로 사건을 해결한 번호를 기반으로 테이블을 세워보라는 힌트였다.

이 말을 보고 어떻게 테이블을 구성해야할 지 생각나서, 직접 테이블을 설계하고 점화식을 세우고, 디버깅을 거친 구현 끝에 맞을 수 있었다.

 

dp[i][j] = 경찰차 1이 마지막으로 i 번째 사건을 해결했고, 경찰차 2가 마지막으로 j 번째 사건을 해결했을 때 그 순간의 최소 이동거리

 

라고 정의하자.

이 정의는 언제나 부분최적해가 되는데, 그 이유는 최적해를 구하는 과정이 두 경찰차의 직전 '위치' = 각 경찰차가 마지막으로 해결한 사건에 따라서만 정해지므로, 이 경우의 수를 모두 저장하면 부분최적해가 됨을 보장할 수 있다.

(직감적으로 이해했다.. 엄밀한 증명은 하지 못했다.)

 

dp 테이블을 비워두고, 예제 입력 1번을 따라가면서 어떻게 채워나가야 할 지 고민하면 다음과 같은 dp 식을 세울 수 있다.

 

- 만약 i == j 라면, 테이블 값은 -1 이다. (두 경찰차가 같은 사건을 해결할 수 없으므로)

 

- 만약 i > j 라면,

i - j = 1 일 때 ==  j번째 이전 사건들을 1번 차가 해결했는지, 2번차가 해결했는지 알 수 없으므로,

즉, 이 시점에서 1번차의 마지막 위치를 알 수 없으므로, 1번차가 마지막으로 위치할 수 있는 모든 경우의 수를 체크한다.

1부터 j-1 까지 모든 k 에 대해 dp[k][j] + dist(k, i) 값의 최소값을 dp[i][j] 로 취한다.

 

i - j > 1 일 때 == i - 1 번째 사건을 1번차가 해결하였음이 보장되므로, 1번차의 직전 위치를 특정할 수 있다.

따라서 dp[i-1][j] + dist(i-1, i) 를 dp[i][j] 값으로 하면 된다.

 

- 만약 i < j 라면, 위 과정을 j 기준으로 그대로 적용하면 된다.

 

이는 시간복잡도에 문제가 없다.

왜냐하면 테이블을 채울 때, 두 사건 번호가 인접한 경우는 i - j = 1, i - j = -1 이렇게 2가지 경우밖에 없으며, 모든 사건에 대해 동일하다.

따라서 O(2*w²) = O(w²) 의 시간복잡도가 걸린다.

이때 w <= 1000 이므로 충분히 1초 안에 돌 수 있다.

 

이것만 구현하는 건 그래도 할만하다.

하지만 여기에 더해 사건을 해결한 순서를 구해야 한다.

즉, 역추적을 해야한다.

 

나는 바텀업으로 풀었는데, 바텀업으로 풀면서 현재 단계를 계산하면, 현재 단계를 계산하기 위해 쓰인 이전 단계를 prev 배열에 저장하는 방식으로 직전 순서를 저장하고, 최종 역추적을 할 때는 prev 노드를 계속 따라가면서 경로를 추적했다.

 

def calc_dist(pos1, pos2):
    return abs(pos1[0]-pos2[0]) + abs(pos1[1]-pos2[1])

INF = 9876543210
n = int(input())
w = int(input())
accidents = [(-1, -1)] + [tuple(map(int, input().split())) for _ in range(w)]
dp = [[-1 for _ in range(w+1)] for _ in range(w+1)]
dp[0][0] = 0
dp[1][0] = calc_dist((1, 1), accidents[1])
dp[0][1] = calc_dist((n, n), accidents[1])

prev_pos = [[None for _ in range(w+1)] for _ in range(w+1)]

for j in range(w+1):
    for i in range(w+1):
        if i == j or dp[i][j] != -1:
            continue
        if i > j:
            if i - j == 1:
                min_value = INF
                min_pos = None
                for k in range(i-1):
                    if k == 0:
                        accidents[k] = (1, 1)
                    if dp[k][j] + calc_dist(accidents[k], accidents[i]) < min_value:
                        min_value = dp[k][j] + calc_dist(accidents[k], accidents[i])
                        min_pos = (k, j)

                dp[i][j] = min_value
                prev_pos[i][j] = min_pos
            elif i - j > 1:
                dp[i][j] = dp[i-1][j] + calc_dist(accidents[i], accidents[i-1])
                prev_pos[i][j] = (i-1, j)

        else: # j > i
            if j - i == 1:
                min_value = INF
                min_pos = None
                for k in range(j-1):
                    if k == 0:
                        accidents[k] = (n, n)
                    if dp[i][k] + calc_dist(accidents[k], accidents[j]) < min_value:
                        min_value = dp[i][k] + calc_dist(accidents[k], accidents[j])
                        min_pos = (i, k)
                dp[i][j] = min_value
                prev_pos[i][j] = min_pos
            elif j - i > 1:
                dp[i][j] = dp[i][j-1] + calc_dist(accidents[j], accidents[j-1])
                prev_pos[i][j] = (i, j-1)

answer = INF
pos = (-1, -1)
for i in range(w):
    if dp[i][w] < answer:
        answer = dp[i][w]
        pos = (i, w)
for j in range(w):
    if dp[w][j] < answer:
        answer = dp[w][j]
        pos = (w, j)

print(answer)
path = []
while w > 0:
    if pos[0] == w:
        path.append(1)
    else:
        path.append(2)

    w -= 1
    pos = prev_pos[pos[0]][pos[1]]
    
for car in reversed(path):
    print(car)

 

정답코드는 다음과 같다.

반복문을 돌 때, j -> i 순으로 돈 이유는, 내가 테이블을 채울 때 j를 고정하고 i부터 변화하는 쪽으로 채우는 방향으로 이해했기 때문이다..

 

 

생각해보니 빠른 입출력 적용을 안했는데, 그래도 통과가 되었고,

빠른 입출력을 적용하고 pypy3 로 제출하니 0.3초에 통과했다!

 

 

괜히 플레가 아니구나 라는 걸 느낀 문제였다.

어떻게 이걸 중학생이 올림피아드 대회에서 푸는 건지 모르겠다.

이 문제를 푼 중학생들이 존경스럽다...