글 읽기 - 왜 오답인지 잘 모르겠습니다.

barcelonamessi 7년 전 0

자료구조는 2차원 벡터를 만들었고

벡터의 자료형은 제가 임의로 만든 사용자 정의형인데 이 자료구조에는

point{

int from;

int to;

int weight;

}

로 시작점, 도착점, 길이를 저장해 두었습니다.

그리고 priority queue 를 만들어서 시작점에서 연결된 간선들을 우선 추가했습니다.

for(int i=0; i<arr.get(start_point).size(); i++){

p_queue.add(arr.get(start_point).elementAt(i));

}

그리고 큐가 빌때까지 가장 작은 크기의 간선을 가져와서 길이를 업데이트 하는데요

while문 내에서

새로운 point에 큐의 제일 앞부분을 가져옵니다.

그리고 탐색을 전혀 하지 않은 부분이고, 도착점이 시작점이 아닌경우에는

해당 점에 길이를 업데이트하고 큐에 그 점에서 연결된 간선을 추가합니다.

또한 탐색을 했던 부분이지만 더 가까워진 부분은 그냥 길이만 업데이트하고

나머지 경우는 그냥 패스합니다. 이렇게 해서 문제에 나온 케이스와 몇가지 케이스는 통과하는데

틀렸다고 나와서 조언을 구해보고자 질문올려봅니다.

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;

public class A1753 {

	public static void main(String[] args) {
		int V;
		int E;
		int start_point;
		class point{
			int from;
			int to;
			int weight;
			point(){}
			point(int from, int to, int weight){
				this.from=from;
				this.to=to;
				this.weight=weight;
			}
		}
		class Get_Line implements Comparator<point>{

			@Override
			public int compare(point arg0, point arg1) {
				
				if(arg0.weight>arg1.weight)
					return 1;
				else if(arg0.weight<arg1.weight)
					return -1;
				return 0;
			}
			
			
		}
		Vector<Vector<point>> arr1 =new Vector<Vector<point>>();
		Scanner scan=new Scanner(System.in);
		
		
		V=scan.nextInt();
		E=scan.nextInt();
		Vector<Vector<point>>arr=new Vector<Vector<point>>(V);
		start_point=scan.nextInt();
		Comparator<point> comparator=new Get_Line();
		PriorityQueue<point> p_queue=new PriorityQueue<point>(300001,comparator);
		for(int i=0; i<=V; i++){
			arr.add(new Vector<point>());
		}
		int[] len=new int[20001];
		
		for(int i=0; i<E; i++){
			int from=scan.nextInt();
			int to=scan.nextInt();
			int weight=scan.nextInt();
			point temp=new point(from,to, weight);
			
//			arr.get(from).add(temp);
			arr.elementAt(from).add(temp);
		}
		
		//primary queue 활용. 큐에 현재 포인트를 넣음
		
		for(int i=0; i<arr.get(start_point).size(); i++){
			p_queue.add(arr.get(start_point).elementAt(i));
			///System.out.println("From " +arr.get(start_point).elementAt(i).from + " to " + arr.get(start_point).elementAt(i).to + " weight : "+ arr.get(start_point).elementAt(i).weight);
		}
		//System.out.println("zz");
		while(!p_queue.isEmpty()){
			point cur=new point();
			cur=p_queue.peek();
			//System.out.println("From " +cur.from + " to " + cur.to + " weight : "+ cur.weight);
			
			//가장 가까운 간선을 가져옴.
			if(len[cur.to]==0 && cur.to!=start_point){//최초 연결된곳.
				len[cur.to]=len[cur.from]+cur.weight;
				p_queue.remove();
				//연결된 점을 추가함.
				for(int i=0; i<arr.get(cur.to).size(); i++){
					p_queue.add(arr.get(cur.to).elementAt(i));
				}
			}else if(len[cur.from]+cur.weight<len[cur.to]){
				p_queue.remove();
				//업데이트 가능한 상황
				len[cur.to]=len[cur.from]+cur.weight;
				//업데이트만함.
			}else{
			p_queue.remove();
			}
				
		}
		for(int i=1; i<=V; i++){
			if(i==start_point)
				System.out.println(0);
			else if(len[i]==0){
				System.out.println("INF");
			}else{
				System.out.println(len[i]);
			}
		}
		

	}
	

}

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