[자바로 푸는 백준] 2618번 경찰차

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

2618번: 경찰차

✅ 플레티넘 Ⅴ

 

🔶 풀이

경찰차 A (1, 1) 과 경찰차 B (N, N) 이 있다.

순서대로 사건이 일어났을 때, 경찰차가 이동하는 최소 거리의 합을 구하라.

 

해당 문제도 dp다.

하지만 점화식을 찾는 dp는 아니고, dfs를 이용해서 문제를 해결해나가면 된다.

 

dp[one][two] 는 "경찰차 A의 위치가 one번째 사건이고, 경찰차 B의 위치는 two번째 사건에 위치하고 있을 때 모든 사건을 해결할때 까지 이동하는 최소 거리의 합"을 나타낸다.

 

dp[0][0] = 경찰차 A, B가 모두 움직이지 않은 경우 현재 위치에서 모든 사건을 해결할 때까지의 이동 거리를 나타낸다.

즉, 정답을 저장한다.

 

첫 번째 사건부터 순서대로 일어남으로 초기에 dfs(1, 0, 0)으로 아래 내용을 호출한다.

public static int dfs (int e, int one, int two) {
    
    // 모든 사건을 이동했을 경우
    if (e > W) return 0;
        
    // 이미 값이 존재할 경우
    if (dp[one][two] != 0) return dp[one][two]; 
		
    int fir = dfs(e+1, e, two) + getDistance(1, one, e); // 경찰차 A가 이동했을 경우
    int sec = dfs(e+1, one, e) + getDistance(2, two, e); // 경찰차 B가 이동했을 경우
		
    return dp[one][two] = Math.min(fir, sec); 
}

사건이 일어날 때마다 경우의 수는 2가지다. (경찰차 A가 이동하거나 경찰차 B가 이동한 경우)

두 가지를 비교한 후에 작은 값을 return 해주면 된다.

 

 

<최종코드>

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

public class Main {
    static int[][] event, dp;
    static int N, W;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        N = Integer.parseInt(br.readLine()); // 맵 크기
        W = Integer.parseInt(br.readLine()); // 사건 수
		
        event = new int[1001][2];
        dp = new int[1001][1001];
		
        for (int i=1; i<=W; i++) {
            st = new StringTokenizer(br.readLine());
			
            event[i][0] = Integer.parseInt(st.nextToken());
            event[i][1] = Integer.parseInt(st.nextToken());
        }

        System.out.println(dfs(1, 0, 0));
		
        int one = 0;
        int two = 0;
        for (int i=1; i<=W; i++) {
            int dist = getDistance(1, one, i);
			
            if (dp[one][two] - dist == dp[i][two]) {
                one = i;
                System.out.println(1);
            } else {
                two = i;
                System.out.println(2);
            }
        }
    }
	
    /**
     * 
     * @param e   N번째 사건
     * @param one 첫 번째 경찰차 이동 횟수
     * @param two 두 번쨰 경찰차 이동 횟수
     * @return
     */
    public static int dfs (int e, int one, int two) {
    
        // 모든 사건을 이동했을 경우
        if (e > W) return 0;
        
        // 이미 값이 존재할 경우
        if (dp[one][two] != 0) return dp[one][two]; 
		
        int fir = dfs(e+1, e, two) + getDistance(1, one, e); // 경찰차 A가 이동했을 경우
        int sec = dfs(e+1, one, e) + getDistance(2, two, e); // 경찰차 B가 이동했을 경우
		
        return dp[one][two] = Math.min(fir, sec); 
    }
	
    /**
     * 
     * @param type  N번쨰 경찰차
     * @param start 출발 위치
     * @param end   도착 위치
     * @return
     */
    public static int getDistance(int type, int start, int end) {
        int[] st = event[start];
        int[] ed = event[end];
		
        // 초기 경찰차 위치 설정
        if (start == 0) {
            if (type == 1) st = new int[] {1, 1}; 
            else st = new int[] {N, N};
        }
		
        return Math.abs(st[0] - ed[0]) + Math.abs(st[1] - ed[1]);
    }
}