글 읽기 - (Java)왜 오답인지 모르겠습니다 ㅠㅠ

hyesoo1104 4년 전 0

1) 우선순위 큐에서 꺼낸 정점방문

2) 방문한 정점과 연결된 정점 확인

3) 최소값으로 업데이트되는 정점 우선순위큐에 추가

위 내용을 우선순위 큐가 빌 때 까지 계속 도는 로직인데 오류가 납니다..

어디가 잘못된걸까요??ㅠㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 백준_1753 {
	static int T, V, E, K;
	static int visited[];
	static int d[]; 
	static ArrayList<int[]>[] con;
	static PriorityQueue<int[]> pq;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		StringTokenizer str = new StringTokenizer(br.readLine().trim());
		V = Integer.valueOf(str.nextToken());
		E = Integer.valueOf(str.nextToken());
		K = Integer.valueOf(br.readLine().trim());
		visited = new int[V+1];
		d = new int[V+1];
		con = new ArrayList[V+1];
		
		for(int i = 0; i<V+1; i++) {
			con[i] = new ArrayList<int[]>();
			d[i] = Integer.MAX_VALUE;
		}
		
		for(int i = 0; i<E; i++) {
			str = new StringTokenizer(br.readLine().trim());
			int a = Integer.valueOf(str.nextToken());
			int b = Integer.valueOf(str.nextToken());
			int c = Integer.valueOf(str.nextToken());
			
			int[] tmp1 = {b,c};
			con[a].add(tmp1); 
		}
		
		pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] > o2[0])
					return 1;
				else 
					return -1;
			}
		});
		
		int[] sNode = {K, 0}; 
		pq.add(sNode);
		d[K] = 0;
		
		while(!pq.isEmpty()) {
			int[] n = pq.poll();
			int vNum = n[0];
			int vDis = n[1];
			visited[vNum] = 1;
			
			for(int[] cNode : con[vNum]) {
				int cNum = cNode[0];
				int cDis = cNode[1];
				
				if(visited[cNum] == 1)
					continue;
				
				if(d[cNum] > vDis+cDis) {
					d[cNum] = vDis + cDis;
					int[] tq = {cNum, d[cNum]}; 
					pq.add(tq);
				}				
			}
		}
		
		for(int i = 1; i<=V; i++) {
			if(d[i] == Integer.MAX_VALUE) {
				bw.write("INF\n");
			}
			else{
				bw.write(d[i]+"\n");
			}
		}
		
		
		br.close();
		bw.close();
	}

}

djm03178 4년 전 0

질문을 올릴 때는 로컬에서 테스트 한 코드 말고, 제출했던 코드를 한 자도 다름없이 그대로 올려주세요. 지금 코드는 클래스명이 Main이 아니라서 아예 컴파일 에러가 나고, 18번째 줄 때문에 제대로 동작이 안 됩니다. 제출하실 땐 당연히 저 둘을 바꾸셨겠죠? 그 바꾼 버전으로 앞으로는 올려주세요.

그 외에 하나만 더 고치면 맞습니다. 거리를 배열의 두 번째 인자에 넣고 있으니, 비교 함수도 당연히 if(o1[0] > o2[0])이 아니라 if(o1[1] > o2[1])이 되어야 합니다.

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

문제

문제

출처

ICPC

(Java)왜 오답인지 모르겠습니다 ㅠㅠ

hyesoo1104 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말