글 읽기 - 2618 경찰차 문제. 시간초과

menyoy 6년 전 0

데이터 개수를 보아 시간초과가 날 것을 감안하고 백트래킹으로 해서 풀었습니다.

DP로 무조건 풀어야할거 같은데 어떻게 디피를 제 코드에서 적용해야할지를 모르겠습니다
혹시 아신다면 알려주시면 감사하겠습니다!!

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Police{
	
	int x;
	int y;
	int processCaseNum; 
	
	
	public Police(int x, int y, int processCaseNum){
		this.x = x;
		this.y = y;
		this.processCaseNum = processCaseNum;
	}
	
	
}
class Incidence{
	
	int x;
	int y;
	
	public Incidence(int x, int y){
		this.x = x;
		this.y = y;
	}

}

public class Main {

	static int police1Distance;
	static int police2Distance;
	static int answer;
	static int dp[][];
	
	static int arr[]; 
	static int answerArr[];
	
	public static  int getDistance(int x1, int y1, int x2, int y2){
		return (Math.abs(x1-x2) + Math.abs(y1-y2));
	}
	
	
	public static void solveMinimumDistance(int incidenceCount, List<Incidence> incidenceList, Police police1, Police police2, int incidenceNumber){
		
		//종료조건
		if(incidenceNumber == incidenceCount){
			
			int tempAnswer = police1Distance + police2Distance;

			if(answer > tempAnswer){
				answer = tempAnswer;
				for(int i = 1 ; i < incidenceList.size() ; i++){
					answerArr[i] = arr[i];	
				}
				
			}

			return;
		}
		
		
		Incidence inc = incidenceList.get(incidenceNumber);
		
		//경찰차 1 처리 
		int distance1 = getDistance(police1.x,police1.y,inc.x,inc.y);
		police1Distance += distance1;
				
		Police newPolice1Place = new Police(inc.x,  inc.y, incidenceNumber);
		newPolice1Place.processCaseNum = incidenceNumber;
		arr[incidenceNumber] = 1;
		solveMinimumDistance(incidenceCount, incidenceList, newPolice1Place, police2, incidenceNumber+1);
		police1Distance -= distance1;
		
		//경찰차 2 처리
		int distance2 = getDistance(police2.x, police2.y, inc.x, inc.y);
		police2Distance += distance2;
		
		Police newPolice2Place = new Police(inc.x,  inc.y,incidenceNumber);
		newPolice2Place.processCaseNum = incidenceNumber;
		arr[incidenceNumber] = 2;
		solveMinimumDistance(incidenceCount, incidenceList, police1, newPolice2Place, incidenceNumber+1);
		police2Distance -= distance2;		
		
		
	}
	
	
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		answer = Integer.MAX_VALUE;
		police1Distance = 0;
		police2Distance = 0;
		
		int N = sc.nextInt();

		int numOfCase = sc.nextInt();
		List <Incidence>caseList = new ArrayList<Incidence>();
		caseList.add(new Incidence(0,0));
		for(int i = 0 ; i < numOfCase ; i++){
			int x = sc.nextInt();
			int y = sc.nextInt();
			Incidence incidence = new Incidence(x, y); 
			caseList.add(incidence);
		}
		arr = new int[caseList.size()];
		answerArr = new int[caseList.size()];
		
		Police police1 = new Police(1, 1,0);
		Police police2 = new Police(N, N,0);
		
		solveMinimumDistance(caseList.size(), caseList, police1, police2, 1);
		System.out.println(answer);
		for(int i = 1 ; i < caseList.size() ; i++){
			System.out.println(answerArr[i]);	
		}
	}

}

djm03178 6년 전 3

경찰차1이 a번째 사건의 위치에, 경찰차2가 b번째 사건의 위치에 가있을 때의 최소 이동 경로를 dp[a][b]로 놓고 BFS를 해보세요.

menyoy 6년 전 0

흠 위의 코드에서 디피를 적용할 수 있긴한건가요ㅠㅠ

djm03178 6년 전 0

백트래킹 상태로는 어렵죠. 방식을 바꾸시는 게 좋을 거 같네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2618 경찰차 문제. 시간초과

menyoy 6년 전 0

djm03178 6년 전 3

menyoy 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말