글 읽기 - 경찰차 최고우선탐색

menyoy 6년 전 0

이 문제를 디피로 풀어야한다고 하는데
최고우선탐색을 적용해보니 상당수의 가지를 미리 제거할 수 있는 사실을 발견했습니다.

근데 런타임에러가 뜨네요

어느부분에서 런타임에러가 뜨는지 도저히 못찾겠습니다

런타임에러가 왜 나는지 찾으면 최고우선탐색으로 해결이 불가능한지 알 수 있을텐데 답답하네요ㅠ

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

class Issue{
	int x;
	int y;
	public Issue(int x, int y){
		this.x = x;
		this.y = y;
	}
}

class Node{
	
	int x1;
	int y1;
	
	int x2;
	int y2;
	
	int cost;
	
	boolean isPolice1;
	boolean isPolice2;
	
	int depth;
	
	int path[];
	
	
	
}

public class Main {

	static int best = Integer.MAX_VALUE;	
	static int countOfCase;
	static int N;
	static List <Integer>bestAnswer = new ArrayList<Integer>();
	public static int getDistance(int x1, int y1, int x2, int y2){
		return Math.abs(x1-x2) + Math.abs(y1-y2);
	}
	public static void bestFirstSearch(Issue arr[], int N){
		
		PriorityQueue<Node>pQ = new PriorityQueue<Node>(new Comparator<Node>() {
			public int compare(Node o1, Node o2){
				if(o1.cost < o2.cost){
					return -1;
				}else if(o1.cost > o2.cost){
					return 1;
				}else{
					return 0;
				}
			}
		});
		
		//사건1일때는 처리를 해줘야함.	
		
		//police1이 사건1담당
		Node police1Node = new Node();
		police1Node.x1 = arr[1].x;
		police1Node.y1 = arr[1].y;
		police1Node.x2 = N;
		police1Node.y2 = N;
		police1Node.isPolice1 = true;
		police1Node.isPolice2 = false;
		police1Node.cost = getDistance(1, 1, police1Node.x1, police1Node.y1);
		police1Node.depth = 1;
		police1Node.path = new int[1001];
		police1Node.path[1] = 1;
		
		//police2가 사건2담당
		Node police2Node = new Node();
		police2Node.x1 = 1;
		police2Node.y1 = 1;
		police2Node.x2 = arr[1].x;
		police2Node.y2 = arr[1].y;
		police2Node.isPolice1 = false;
		police2Node.isPolice2 = true;
		police2Node.cost = getDistance(N, N, police2Node.x2, police2Node.y2);
		police2Node.depth = 1;
		police2Node.path = new int[1001];
		police2Node.path[1] = 2;
		
		pQ.offer(police1Node);
		pQ.offer(police2Node);
		
		
		
		while(!pQ.isEmpty()){
			
			Node pollNode = pQ.poll();

			if(pollNode.depth == countOfCase){
//				System.out.println("호출횟수");
				if(best > pollNode.cost){
					best = pollNode.cost;
					if(bestAnswer.size() != 0){
						bestAnswer =  new ArrayList<Integer>();
					}
					for(int i = 1 ; i <= countOfCase ; i++){
						bestAnswer.add(pollNode.path[i]);
					}
				}else{
//					System.out.println("가지치기의 결과");
					continue;
				}
			}
			int newLevel = pollNode.depth + 1;
			
			if(newLevel <= countOfCase){
				
				//polic1이 담당
				Node newPolice1Node = new Node();
				newPolice1Node.depth =newLevel;
				newPolice1Node.x1 = arr[newLevel].x;
				newPolice1Node.y1 = arr[newLevel].y;
				newPolice1Node.x2 = pollNode.x2;
				newPolice1Node.y2 = pollNode.y2;
				newPolice1Node.isPolice1 = true;
				newPolice1Node.isPolice2 = false;
				newPolice1Node.cost = pollNode.cost + getDistance(newPolice1Node.x1, newPolice1Node.y1, pollNode.x1, pollNode.y1);
				
				newPolice1Node.path = new int[1001];
				for(int i = 1 ; i <= countOfCase ; i++){
					newPolice1Node.path[i] = pollNode.path[i]; 
				}
				newPolice1Node.path[newLevel] = 1;
				
				
				//믿고 거름
				if(best > newPolice1Node.cost){
					if(newPolice1Node.depth == countOfCase){
						if(best > newPolice1Node.cost){
							best = newPolice1Node.cost;	
							if(bestAnswer.size() != 0){
								bestAnswer =  new ArrayList<Integer>();
							}
							for(int i = 1 ; i <= countOfCase ; i++){
								bestAnswer.add(newPolice1Node.path[i]);
							}
						}
					}
					pQ.offer(newPolice1Node);
				}else{
//					System.out.println("가지치기의 결과");
				}
				
				
				//police2가 담담
				Node newPolice2Node = new Node();
				newPolice2Node.depth = newLevel;
				newPolice2Node.x1 = pollNode.x1;
				newPolice2Node.y1 = pollNode.y1;
				newPolice2Node.x2 = arr[newLevel].x;
				newPolice2Node.y2 = arr[newLevel].y;
				newPolice2Node.isPolice1 = false;
				newPolice2Node.isPolice2 = true;
				newPolice2Node.cost = pollNode.cost + getDistance(newPolice2Node.x2, newPolice2Node.y2, pollNode.x2, pollNode.y2);
				
				newPolice2Node.path = new int[1001];
				for(int i = 1 ; i <= countOfCase ; i++){
					newPolice2Node.path[i] = pollNode.path[i]; 
				}
				newPolice2Node.path[newLevel] = 2;

				
				//믿고 거름
				if(best > newPolice2Node.cost){
					if(newPolice2Node.depth == countOfCase){
						if(best > newPolice2Node.cost){
							best = newPolice2Node.cost;	
							if(bestAnswer.size() != 0){
								bestAnswer =  new ArrayList<Integer>();
							}
							for(int i = 1 ; i <= countOfCase ; i++){
								bestAnswer.add(newPolice2Node.path[i]);
							}
						}
					}
					pQ.offer(newPolice2Node);
				}else{
//					System.out.println("가지치기의 결과");
				}
			}


		}
		System.out.println(best);
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		countOfCase = sc.nextInt();
		
		Issue []caseArr = new Issue[1001];
		for(int i = 1 ; i <= countOfCase ; i++){
			
			int x = sc.nextInt();
			int y = sc.nextInt();
			Issue issue = new Issue(x,y);
			caseArr[i] = issue;
		}
	
		bestFirstSearch(caseArr, N);
		for(int i = 0 ; i < bestAnswer.size() ; i++){
			System.out.println(bestAnswer.get(i));
		}
	}
}

yclock 6년 전 1

랜덤 데이터만 넣어도 시간안에 돌지 않습니다...

#include <bits/stdc++.h>
using namespace std;

int main() {
	srand(time(0));
	puts("1000\n1000");
	for(int i = 0; i < 1000; i++)
		printf("%d %d\n", rand()%1000 + 1, rand()%1000 + 1);
	return 0;
}

menyoy 6년 전 0

아 댓글달아주셔서 감사합니다 혹시 백준사이트에서 시간초과가 나도 런타임에러인가요?

menyoy 6년 전 0

으아 눈으로 직접확인했습니다 디피로 풀었을 때와의 차이점을..

yclock 6년 전 2

5초동안 돌려도 답이 안나올 정도로 탐색을 한다면, 그만큼 메모리도 많이 쓰지 않을까요?

시간 사용량과 메모리 사용량이 비례하는 소스코드라서, TLE와 MLE가 서로 동치일 것 같습니다.

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

문제

문제

출처

ICPC

경찰차 최고우선탐색

menyoy 6년 전 0

yclock 6년 전 1

menyoy 6년 전 0

menyoy 6년 전 0

yclock 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말