[JAVA]백준 2618번: 경찰차

www.acmicpc.net/problem/2618

2618번: 경찰차

 

1. 문제 설명

 

(1,1)과 (N, N)에 두 대의 경찰차가 대기하고 있다.

 

그 후 W개의 사건들의 좌표들이 주어질 때 사건들이 발생한 순서대로 경찰차들이 이동하는 거리의 합의 최솟값을 출력하고 경로를 출력하는 문제이다.

 

2. 풀이

 

 

점화식보다 재귀함수로재귀 함수로 푸는 것이 더 간단해서 재귀 함수로 문제를 풀었다. 

 

재귀 함수의 경우 O(N^2)의 시간복잡도를 가지지만 점화식의 경우 O(N^3)을 가진다.

 

점화식의 경우

 

"dp[x][y] = 첫 번째 경찰차의 위치가 x번째 사건이고 두 번째 경찰차의 위치가 y번째 사건일 때까지의 이동하는 거리의 합의 최솟값"이라 한다면

 

• x==y-1 => dp[x][y]=min(dp[x][z]+(사건 z에서 사건 y까지의 이동거리) (0 <=z <=x-1))
• x==y+1 => dp [x][y]=min(dp [z][y]+(사건 z에서 사건 x까지의 이동거리) (0 <=z <=y-1))
• x> y => dp [x][y]=dp [x-1][y]+(사건 x-1에서 사건 x까지의 이동거리)
• x <y => dp [x][y]=dp [x][y-1] + (사건 y-1에서 사건 y까지의 이동거리)

으로 풀 수 있다.

 

재귀 함수의 경우

 

"dp [x][y] = 첫 번째 경찰차의 위치가 x번째 사건이고 두 번째 경찰차의 위치가 y번째 사건에 있을 때 현재 위치에서 사건을 끝까지 해결할때 까지 이동하는 거리의 합의 최솟값" 이라 한다면

 

다음 k번째 사건을 첫번째 경찰차가 해결할 경우와 두번째 경찰차가 해결할 경우를 비교하여 최솟값을 배열에 저장하면 된다.

 

 

추적은 dp 배열을 이용해서 할 수 있다.

 

dp [0][0]에는 첫 번째 경찰차와 두번째 경찰차 모두 움직이지 않았을 때 현재 위치에서 끝까지 사건을 해결할때까지의 거리의 합의 최솟값 즉, 답이 저장되어 있다. 

 

다음으로 이동할 수 있는 경우는 2가지가 있는데 첫 번째 경찰차가 첫번째 사건을 맡는 경우 (dp[1][0]) 두번째 경찰차가 첫번째 사건을 맡는 경우(dp [0][1])이 있다.

 

만약 dp [1][0]과 첫 번째 경찰차가 처음 시작점에서 첫번째 사건까지의 이동거리를 합한 것이 dp[0][0]과 같다면 첫번째 경찰차가 움직인 것이고 아니라면 두 번째 경찰차가 움직인 것이다.

 

첫 번째 경찰차가 움직인 것이라면 기준점이 dp[1][0]으로 바뀌고 두 번째 경찰차가 움직인 것이라면 dp[0][1]로 변경된다.

 

이러한 방법으로 첫번째 경찰차 또는 두번째 경찰차가 마지막 위치까지 도달할 때까지 추적해 출력하면 된다.

 

 

3. 코드

 

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static int[][] list=new int[1002][2];
    public static int event_num,line_num;
    public static int[][] dp=new int[1002][1002];

    public static void main(String[] args) throws IOException {

        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        line_num=Integer.parseInt(br.readLine());
        event_num=Integer.parseInt(br.readLine());


        for(int x=1;x<=event_num;x++){
            StringTokenizer st=new StringTokenizer(br.readLine());

            list[x][0]=Integer.parseInt(st.nextToken());
            list[x][1]=Integer.parseInt(st.nextToken());
        }





        bw.write(String.valueOf(police(1,0,0))+"\n");

        int index_one=0;
        int index_two=0;


        for(int index=1;index<=event_num;index++){

            int one_remain=distance(1,index_one,index);

            if(dp[index_one][index_two]-one_remain==dp[index][index_two]){
                index_one=index;
                bw.write("1\n");
            }else{
                index_two=index;
                bw.write("2\n");
            }

        }

        bw.flush();
        bw.close();
        br.close();



    }


    public static int police(int index,int one,int two){
        if(index>event_num)
            return 0;



        if(dp[one][two]!=0)
            return dp[one][two];



        int one_move=police(index+1,index,two)+distance(1,one,index);

        int two_move=police(index+1,one,index)+distance(2,two,index);


        dp[one][two]=Math.min(one_move,two_move);


        return dp[one][two];

    }

    public static int distance(int sep,int start,int end){


        int x_start=list[start][0],y_start=list[start][1],x_end=list[end][0],y_end=list[end][1];

        if(start==0){
            if(sep==1){
                x_start=y_start=1;
            }else{
                x_start=y_start=line_num;
            }
        }

        return Math.abs(x_start-x_end)+Math.abs(y_start-y_end);



    }
}