글 읽기 - 계속 틀렸다고 나오는데 뭐가 잘못되었을까요??

bonoxtwo 7년 전 0

여러 테스트 케이스를 사용해서 테스트 해봐도 뭐가 잘못된지 모르겠네요 ㅠㅠ

import java.util.*;
public class Main{
	static int n, m;
	static int map[][];
	static int dist[];
	static boolean visited[];
	static int INF=987654321;
	
	public static void main(String[] args){
		Scanner input=new Scanner(System.in);
		
		int i;
		int s, e, w;
		n=input.nextInt();    //city
		m=input.nextInt();    //bus
		
		map=new int[n+1][n+1];
		dist=new int[n+1];
		visited=new boolean[n+1];
		
        //initailize
		for(i=0;i<=n;i++){
			Arrays.fill(map[i], INF);
		}
		Arrays.fill(dist, INF);
		Arrays.fill(visited, false);
		
        //input map values
		for(i=0;i<m;i++){
			s=input.nextInt();
			e=input.nextInt();
			w=input.nextInt();
			if(map[s][e] > w)
				map[s][e]=w;
		}
		
		s=input.nextInt();
		e=input.nextInt();
		
		dist[s]=0;
		search(s,e);
		System.out.println(dist[e]);
	}

	public static void search(int start, int end) {
		if(start==end || start==INF)
			return;
		visited[start]=true;
		
		int min=INF;
		
		for(int i=1;i<=n;i++){
			if(map[start][i]!=INF && !visited[i]){
				if(dist[i]>dist[start]+map[start][i]){
					dist[i]=dist[start]+map[start][i];
				}
				
				if(min==INF||dist[min]>dist[i])
					min=i;
			}
		}
		search(min, end);
		return;
	}
}

plzrun 7년 전 0

x->y로 갈때
x->a->y, x->b->y 두 경로가 있다고 해볼게요,
그런데 b로 가는 길이 더 짧은데 탐색순서상 a부터 보게된다면,
(즉, x->a가중치가 1이고, a->y가 100000인데, x->b가 100이고 b->y는 1인 경우죠)

x->a->y하면서 x,a,y모두 visited에 체크가 될거에요. 하지만 그떄의 dist값은 최소가 아님에도 전부 체크가 되어있는 상태죠.
이 상태에서 b->y를 들어가려고 해봐야 visit이 체크되어있으니 들어갈 수가 없어요.. 그럼 갱신되지 않죠.
visited라는 배열이 반드시 최단거리를 업뎃해주고 난다음에 체크가 되어야 할거에요.
그러므로 그냥 반복문을 도는게 아니라 민힙을 써서 가장 작은거리부터 뱉어주게 해야 할것 같네요.
그게 다익스트라의 원리이기도 하구요.

plzrun 7년 전 0

그리고 이 코드는 x->a->y까지 들어가고 나면 x->b를 더 탐색해볼 수도 없는것 같군요.

bonoxtwo 7년 전 0

아 정말 그렇네요! 감사합니다!!

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

문제

문제

출처

ICPC

계속 틀렸다고 나오는데 뭐가 잘못되었을까요??

bonoxtwo 7년 전 0

plzrun 7년 전 0

plzrun 7년 전 0

bonoxtwo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말