[백준] 단계별로 풀어보기(단계:27, 동적 계획법과 최단거리 역추적,JAVA)2618번, 경찰차

문제 링크

2618번: 경찰차

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 증가하는 수열 중 가장 긴 수열의 길이를 결과로 출력해야 합니다.

 

배열

 

accident[][2] : 입력되는 사건들의 좌표를 저장하는 배열

 

DP[i][j] : i는 첫번째 경찰차 위치, j는 두번째 경찰차 위치일 때 거리의 합이 최소인 값을 저장하는 배열

 

accident 배열에 인덱스 1부터 사고의 위치를 저장하였습니다.

 

예제입력 1에서 경찰차가 이동하는 경우의 수를 표현하면

 

네모 칸에 있는 값들은 DP를 가리키는 i와 j입니다.

 

위와 같이 DP를 이용하면 동일한 연산을 반복하지 않고 거리의 최소합을 구할 수 있습니다.

 

 

처음 두 경찰차의 시작을 DP[0][0]에 저장합니다.

 

첫 번째 사고 위치를 첫 번째 경찰차가 이동하면 DP[1][0]첫 번째 사고 위치를 두 번째 경찰차가 이동하면 DP[0][1]

 

 

각 좌표의 거리는

|현재 위치 x값 - 목표위치 x값| + |현재 위치 y값 - 목표 위치 y값| = 거리

 

경우의 수를 재귀와 DP를 이용하여 다음 사건의 위치를 첫 번째 경찰차 갈 때와 두 번째 경찰차가 갈 때의 경우의 거리의 합을 비교하여 거리의 최소합을 구하도록 구현하였습니다.

 

어떤 경찰차가 사건들을 처리했는지 출력할 때

DP는 최소 거리의 합이 저장되어있기 때문에

첫 번째 경찰차가 다음 사건에 가는 거리를 이용하여 첫 번째 경찰차가 갔는지 두 번째 경찰차가 갔는지 확인하였습니다.

 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력되는 문자열 N과W, W개의 사건의 위치를 저장합니다.

2. DP와 재귀를 이용하여 모든 경우를 비교하여 거리의 최소 합을 구합니다.

3. 최소 거리의 합을 결과로 출력합니다.

4. 사건이 어떤 경찰차가 처리했는지 확인하기 위해 DP에 저장된 값의 거리를 이용하여 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 W개의 사건 좌표를 나누었습니다.
• 재귀와 DP[]를 이용하여 거리의 최소합을 구하는 cal 함수를 실행하였습니다.
• 각 좌표별 거리를 구하는 distance함수를 실행하였습니다.
• BufferedWriter에 cal함수의 결과인 거리의 최소합을 저장하였습니다.
• BufferedWriter에 DP와 첫번째 경찰차와 다음 사건의 거리를 이용하여 사건을 해결한 경찰차를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal 함수는 재귀와 DP를 이용하여 거리의 최소합을 반환하였습니다.
• distance함수는 각 좌표 거리를 구하는 공식을 이용하여 거리를 반환하였습니다.

import java.io.*;
import java.util.*;
public class Main{
	static int N,W;
	static int[][] accident;	//사건의 좌표 저장 배열
	static int[][] DP;		//각 경찰차 위치에 따른 최소 거리의 합 저장하는 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
        	//-----입력값 저장 및 배열 초기화-------
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		W = Integer.parseInt(br.readLine());
		DP = new int[W+1][W+1];
		accident = new int[W+1][2];
		for(int i=1;i<=W;i++) {
			st = new StringTokenizer(br.readLine()," ");
			accident[i][0] = Integer.parseInt(st.nextToken());
			accident[i][1] = Integer.parseInt(st.nextToken());
		}
		int result = cal(0,0,1);		//경찰차 거리의 최소 합 구하기
		bw.write(result + "\n");	//거리의 최소합 BufferedWriter 저장
		//사건 어떤 경찰차가 도착했는지 확인
		int one = 0;
		int two = 0;
		for(int i=1;i<=W;i++) {
			int width = distance(one,i,true);	//첫번째 경찰차 위치 구하기
			if(DP[one][two]-width == DP[i][two]) {	//DP 이용하여 첫번째 경찰차가 갔는지 확인
				bw.write("1\n");
				one = i;
			}
			else {	//첫 번째 경찰차가 가지 않았을 때
				bw.write("2\n");
				two = i;
			}
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//------재귀와 DP를 이용하여 경찰차 거리의 최소합을 구하는 함수------
	static int cal(int first, int second, int next) {
		if(next==W+1) 	//마지막 사건 이후
			return 0;
		
		if(DP[first][second]!=0)		//이미 연산했었던 값인 경우
			return DP[first][second];
		//첫번째 경찰차가 다음 사건 갈 경우
		int first_move_next = cal(next,second,next+1) + distance(first,next,true);
        	//두번째 경찰차가 다음 사건 갈 경우
		int second_move_next = cal(first,next,next+1) + distance(second,next,false);
		//두 경우 비교하여 거리의 최소 합 구하기
		DP[first][second] = Math.min(first_move_next, second_move_next);
		
		return DP[first][second];
	}
    	//각 좌표별 거리 구하기
	static int distance(int cur, int next, boolean check) {
		int cur_x = accident[cur][0];
		int cur_y = accident[cur][1];
		int next_x = accident[next][0];
		int next_y = accident[next][1];
		if(cur==0) {
			if(check)
				cur_x = cur_y = 1;
			else
				cur_x = cur_y = N;
		}
		return Math.abs(cur_x - next_x) + Math.abs(cur_y - next_y);
	}
}