알고리즘/다이나믹 프로그래밍(DP)

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

K.두부 2023. 5. 15. 12:00
반응형

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

 

2618번: 경찰차

첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄

www.acmicpc.net

✅ 플레티넘 Ⅴ

 

🔶 풀이

경찰차 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]);
}
}

반응형