[JAVA] 백준 2618 경찰차

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

문제분석

좀 말도안되는 난이도 문제라고 생각한다...

이 문제를 분석하다보면, "경찰차는 무조건 사건 장소 혹은 처음 자리에만 위치해야 한다"는 무조건 성립한다는 것을 알 수있다.

따라서, 인덱스를 '경찰차의 마지막 해결 사건 순서' 로 지정했다. 경찰차가 2개니까 2차원 배열로 [1번경찰차][2번경찰차]로 구상했다. 값으로는 해당 사건들을 해결하기 위한 최소 이동거리를 저장한다.

처음에는 단순 for문을 2중으로 돌려서, [1][0], [1][2]...[1][N]까지 나아가면 될 것 이라는 생각을 했었다. 하지만 도무지 답이 나오지 않았기도 하고, 예외처리가 너무나도 많이 필요했다.

그리고 알게 된 사실은, 다음 사건을 max(a,b)+1로 지정한 뒤, 1번째 경찰차 혹은 2번째 경찰차가 해당 사건을 맡는 경우를 확인하면 되는 것 이였다. 따라서, for문의 목적은 dp[a][b]를 구하는 것이 아니라, dp[max(a+b)+1][b], dp[a][max(a+b)+b]를 구하는 것이다.

구하기 위한  방법은? dp[a][b]에 저장된 값+a와 다음 사건 거리, b와 다음 사건 거리 를 구해 저장해주면 된다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int W, N;
    static int[][] ev;
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        W = Integer.parseInt(br.readLine().trim());
        N = Integer.parseInt(br.readLine().trim());
        ev = new int[N+1][2];
        StringTokenizer st;
        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine());
            ev[i][0] = Integer.parseInt(st.nextToken());
            ev[i][1] = Integer.parseInt(st.nextToken());
        }

        // dp[a][b] = 사건 max(a,b)까지 처리,
        // 1번차 마지막=a, 2번차 마지막=b 일 때의 누적 최소 이동거리
        int[][] dp = new int[N+1][N+1];
        for(int[] row: dp) Arrays.fill(row, INF);
        dp[0][0] = 0;

        // 경로 복원을 위한 parent와 담당자 기록
        // parA[a][b], parB[a][b] = (a,b) 상태의 직전 상태
        // who[a][b] = 이 상태로 올 때 사건 t를 맡은 경찰 (1 또는 2)
        int[][] parA = new int[N+1][N+1];
        int[][] parB = new int[N+1][N+1];
        int[][] who  = new int[N+1][N+1];
        for(int[] r: parA) Arrays.fill(r, -1);
        for(int[] r: parB) Arrays.fill(r, -1);
        for(int[] r: who)  Arrays.fill(r,  0);

        for(int a=0; a<=N; a++){
            for(int b=0; b<=N; b++){
                int cur = dp[a][b];
                if(cur == INF) continue;
                int t = Math.max(a, b) + 1;
                if(t > N) continue;

                // 사건 t를 1번차가 처리 -> (t, b)
                int cost1 = cur + dist1(a, t);
                if(cost1 < dp[t][b]){
                    dp[t][b] = cost1;
                    parA[t][b] = a;
                    parB[t][b] = b;
                    who[t][b]  = 1;
                }

                // 사건 t를 2번차가 처리 -> (a, t)
                int cost2 = cur + dist2(b, t);
                if(cost2 < dp[a][t]){
                    dp[a][t] = cost2;
                    parA[a][t] = a;
                    parB[a][t] = b;
                    who[a][t]  = 2;
                }
            }
        }
        // 최종 상태 선택 (max(a,b)=N 중 최솟값)
        int ans = INF;
        int endA = -1, endB = -1;
        for(int a=0; a<=N; a++){
            if(dp[a][N] < ans){
                ans = dp[a][N];
                endA = a; endB = N;
            }
        }
        for(int b=0; b<=N; b++){
            if(dp[N][b] < ans){
                ans = dp[N][b];
                endA = N; endB = b;
            }
        }
        // 경로 복원 (뒤에서부터)
        int[] assign = new int[N+1]; // assign[t] = 1 or 2
        int a = endA, b = endB;
        int t = Math.max(a, b);
        while(t > 0){
            assign[t] = who[a][b];
            int pa = parA[a][b];
            int pb = parB[a][b];
            a = pa; b = pb;
            t--;
        }
        // 출력
        bw.write(String.valueOf(ans));
        bw.newLine();
        for(int i=1;i<=N;i++){
            bw.write(String.valueOf(assign[i]));
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
    static int dist1(int from, int to){ // 1번차 기준 거리: from==0이면 (1,1)
        int x1 = (from==0) ? 1 : ev[from][0];
        int y1 = (from==0) ? 1 : ev[from][1];
        int x2 = ev[to][0], y2 = ev[to][1];
        return Math.abs(x1-x2) + Math.abs(y1-y2);
    }
    static int dist2(int from, int to){ // 2번차 기준 거리: from==0이면 (W,W)
        int x1 = (from==0) ? W : ev[from][0];
        int y1 = (from==0) ? W : ev[from][1];
        int x2 = ev[to][0], y2 = ev[to][1];
        return Math.abs(x1-x2) + Math.abs(y1-y2);
    }
}