Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

27. 동적 계획법과 최단거리 역추적

지금까지는 최솟값, 최댓값, 최단거리만 찾았습니다. 이번에는 실제 최적해와 최단경로를 찾아 봅시다.

Java / Python

5. 경찰차

2618번

조금 더 복잡한 DP 문제

이번 문제는 처리해야 할 사건들이 순서대로 주어질 때, 두 대의 경찰차가 이동하는 거리의 합을 최소화 하도록 사건들을 맡기는 프로그램을 작성하는 문제입니다.

예를 들어 앞의 그림처럼 N=6인 경우, 처리해야 하는 사건들이 3개 있고 그 사건들이 발생된 위치 를 순서대로 (3, 5), (5, 5), (2, 3)이라고 하자. (3, 5)의 사건을 경찰차2에 맡기고 (5, 5)의 사건도 경찰차2에 맡기며, (2, 3)의 사건을 경찰차1에 맡기면 두 차가 이동한 거리의 합은 4 + 2 + 3 = 9가 되 고, 더 이상 줄일 수는 없다.

• Java

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

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

		bw.write(policeSolution(1,0,0)+"\n");
        
		int firstidx = 0;
		int secondidx = 0;

		for(int i = 1; i <= W; i++) {
			int dist1 = distance(1, firstidx, i);
			
			if(dp[firstidx][secondidx] - dist1 == dp[i][secondidx]) {
				firstidx = i;
				bw.write("1\n");
			}else {
				secondidx = i;
				bw.write("2\n");
			}
			
		}
           
		bw.flush();
		br.close();
		bw.close();
	}	
	
	static int policeSolution(int event, int first, int second) {
		if(event > W) return 0;
		
		if(dp[first][second] != 0) return dp[first][second];
		
		int one = policeSolution(event+1, event, second) + distance(1, first, event);
		int two = policeSolution(event+1, first, event) + distance(2, second, event);
		
		dp[first][second] = Math.min(one, two);
		
		return dp[first][second];
	}
	static int distance(int type, int start, int end) {
		int x_start = position[start][0];
		int y_start = position[start][1];
		int x_end = position[end][0];
		int y_end = position[end][1];

		if(start == 0) {
			if(type == 1) x_start = y_start = 1;
			else x_start = y_start = N;
		}
		
		return Math.abs(x_start-x_end)+Math.abs(y_start-y_end);
	}
}

• Python

java와 비슷하게 풀려고 많이 시도했었는데, TypeError를 고치지 못해 조금 다른 방식으로 풀었습니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# main
N = int(input()) # 도로 N x N 
W = int(input()) # 사건 개수
position = [(1,1),(N,N)]
for _ in range(W):
    position.append(tuple(map(int,input().split())))
dp = [[-1 for _ in range(W+2)] for _ in range(W+2)]

def solution(i,j):
    if i > W or j > W: return 0
    if dp[i][j] != -1: return dp[i][j]
    
    tmp = max(i,j) + 1
    ni = solution(tmp,j) + abs(position[tmp][0]-position[i][0]) + abs(position[tmp][1]-position[i][1])
    nj = solution(i,tmp) + abs(position[tmp][0]-position[j][0]) + abs(position[tmp][1]-position[j][1])
    dp[i][j] = min(ni,nj)
    return dp[i][j]

def backtracking(x,y):
    if x > W or y > W: return
    nc = max(x,y) + 1
    nx = abs(position[nc][0]-position[x][0]) + abs(position[nc][1]-position[x][1])
    ny = abs(position[nc][0]-position[y][0]) + abs(position[nc][1]-position[y][1])

    if dp[nc][y]+nx < dp[x][nc]+ny:
        print(1)
        backtracking(nc,y)
    else:
        print(2)
        backtracking(x,nc)
    return

# result
print(solution(0,1))
backtracking(0,1)