[백준] 2618번 - 경찰차 (Platinum 5)

문제 링크

백준 2618번 - 경찰차 (Platinum 5)

문제 설명

두 대의 경찰차가 있다. 경찰차 1은 처음에 (1, 1)에 있으며, 경찰차 2는 처음에 (N, N)에 있다.
W개의 사건을 두 경찰차의 이동거리의 합을 최소화하면서 순서대로 처리하고자 한다.
각 사건이 일어난 위치는 순서대로 점 $X_1, X_2, \cdots, X_W$이다.
단, 두 점 (a, b)와 (c, d) 사이의 거리는 유클리드 거리가 아닌, 택시 거리로 주어진다.
즉, d((a, b), (c, d)) = |a - c| + |b - d|이다.

두 경찰차의 이동거리의 합이 최솟값과 이 때 각 사건을 맡은 경찰차 번호(1 또는 2)를 순서대로 출력하시오.

정답 코드 및 설명

최종적으로 각 사건을 맡은 경찰차 번호도 출력해야하므로, DP를 사용하되 역추적이 가능하도록 해야한다.
아래 풀이에서는 1번 경찰차가 해결한 최종 사건이 i번째 사건이고 2번 경찰차가 해결한 최종 사건이 j번째 사건일 때 두 경찰차가 이동한 거리의 합의 최소가 되는 경우를 paths[i][j]로 두었다. 여기서 0번째 사건은 각 경찰차의 초기 위치에 해당한다.
또한, 역추적을 위해 paths[i][j]에는 최소 이동거리의 합만이 아닌, 직전의 위치도 저장하였다.

이제 점화식을 세워보자.
설명의 편의를 위해, paths[i][j]에 저장된 최소 이동거리를 그냥 paths[i][j]로 표현하였다.

1. 1번 경찰차가 i번 사건을 처리한 것이 마지막 이동인 경우 1-1. 2번 경찰차의 마지막 위치 j < i - 1인 경우
   • 1번 경찰차가 i - 1번 사건을 처리하고, 여기서 i번 사건을 처리하러 이동한 경우만이 가능하다.
   • 직전 위치는 1번 경찰차 i - 1, 2번 경찰차 j
   • 최소 이동거리는 paths[i - 1][j] + dist($X_{i-1}, X_i$) 1-2. 2번 경찰차의 마지막 위치 j = i - 1인 경우
   • 1번 경찰차가 k(< j)번 사건을 처리하고, 여기서 i번 사건을 처리하러 이동한 경우이다.
   • 각 경우의 최소 이동거리는 paths[k][j] + dist($X_{k}, X_i$)
   • $k = 1, 2, \cdots, j - 1$에 대해 위에서 구한 이동거리 중 최소인 경우를 택하면 된다.
2. 2번 경찰차가 j번 사건을 처리한 것이 마지막 이동인 경우
   • 1번 경우와 거의 유사하게 두 경우를 나누어서 처리할 수 있다. i, j만 바뀐 상황이다.

위의 점화식을 DP를 통해 구하는 과정은 코드의 43행 ~ 86행을 참조하면 된다.

마지막 사건을 처리한 이후의 경찰차 1, 2의 위치로 가능한 조합은 여러가지이므로, 이 중 최적인 경우를 구해야 사건을 처리하기 위한 이동거리의 합의 최솟값을 구할 수 있다.
paths[0][W] ~ paths[W-1][W], paths[W][0] ~ paths[W][W-1]의 최솟값을 찾으면 이를 해결할 수 있다.
paths[i][j]가 최솟값이었다면, 마지막 사건을 처리한 이후 경찰차 1의 위치는 i, 경찰차 2의 위치는 j인 것이다.
이 과정은 코드의 88행 ~ 105행에 해당한다.

이제 각 경찰차의 위치를 역추적하자.
각 지점에 도달하기 위한 최적 경로에서의 직전의 위치를 모두 저장해두었으므로, 이 과정은 쉽다.
paths[i][j]에 저장된 직전의 위치를 따라가면서 마지막 사건을 경찰차 1이 처리했는지, 경찰차 2가 처리했는지를 확인하고 스택에 넣어준다. 이렇게 하면 스택에는 마지막 사건의 정보부터 역순으로 들어가게 된다.
스택은 LIFO 자료구조이므로, 원소를 순서대로 꺼내서 출력하면 첫 사건부터 출력될 것이다.
이 과정은 코드의 108행 ~ 117행에 해당한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ2618 {
    int n, w;
    int[][] points1, points2;
    Path[][] paths;

    static class Path {
        final int[] before;
        final int minDist;

        Path(int[] before, int minDist) {
            this.before = before;
            this.minDist = minDist;
        }
    }

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        w = Integer.parseInt(br.readLine());
        points1 = new int[w + 1][];
        points2 = new int[w + 1][];
        points1[0] = new int[]{1, 1};
        points2[0] = new int[]{n, n};
        StringTokenizer st;
        for (int i = 0; i < w; i++) {
            st = new StringTokenizer(br.readLine());
            points1[i + 1] = points2[i + 1] =
                    new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
        }
        paths = new Path[w + 1][w + 1];
    }

    int dist(int[] point1, int[] point2) {
        return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
    }

    Path getPath(int i, int j) {
        // paths[i][j] : 1번 경찰차의 현 위치 i, 2번 경찰차의 현 위치 j
        // 초기 상태
        if (i == 0 && j == 0)
            return paths[i][j] = new Path(new int[]{0, 0}, 0);
        if (paths[i][j] != null)
            return paths[i][j];
        // 마지막 이동 : 1번 i - 1 -> i
        if (j < i - 1) {
            int minDist = getPath(i - 1, j).minDist + dist(points1[i], points1[i - 1]);
            return paths[i][j] = new Path(new int[]{i - 1, j}, minDist);
        }
        // 마지막 이동 : 2번 j - 1 -> j
        if (i < j - 1) {
            int minDist = getPath(i, j - 1).minDist + dist(points2[j], points2[j - 1]);
            return paths[i][j] = new Path(new int[]{i, j - 1}, minDist);
        }
        // 마지막 이동 : 1번 ? -> i
        if (j == i - 1) {
            int minDist = getPath(0, j).minDist + dist(points1[i], points1[0]);
            int minIndex = 0;
            for (int k = 1; k < j; k++) {
                int dist = getPath(k, j).minDist + dist(points1[i], points1[k]);
                if (dist < minDist) {
                    minDist = dist;
                    minIndex = k;
                }
            }
            return paths[i][j] = new Path(new int[]{minIndex, j}, minDist);
        }
        // 마지막 이동 : 2번 ? -> j
        if (i == j - 1) {
            int minDist = getPath(i, 0).minDist + dist(points2[j], points2[0]);
            int minIndex = 0;
            for (int k = 1; k < i; k++) {
                int dist = getPath(i, k).minDist + dist(points2[j], points2[k]);
                if (dist < minDist) {
                    minDist = dist;
                    minIndex = k;
                }
            }
            return paths[i][j] = new Path(new int[]{i, minIndex}, minDist);
        } else return null;
    }

    int[] finalPostion() {
        int minDist = Integer.MAX_VALUE;
        int[] position = new int[2];
        for (int i = 0; i < w; i++) {
            int dist = getPath(i, w).minDist;
            if (dist < minDist) {
                minDist = dist;
                position[0] = i;
                position[1] = w;
            }
            dist = getPath(w, i).minDist;
            if (dist < minDist) {
                minDist = dist;
                position[0] = w;
                position[1] = i;
            }
        }
        return position;
    }

    void traceback(int[] position) {
        System.out.println(paths[position[0]][position[1]].minDist);
        Stack<Integer> police = new Stack<>();
        for (int i = w; i > 0; i--) {
            if (position[0] == i) police.push(1);
            else police.push(2);
            position = getPath(position[0], position[1]).before;
        }
        while (!police.isEmpty())
            System.out.println(police.pop());
    }

    void solution() throws IOException {
        input();
        traceback(finalPostion());
    }

    public static void main(String[] args) throws IOException {
        new BOJ2618().solution();
    }
}