글 읽기 - [JAVA] 다익스트라 틀린 이유 좀 봐주세요 ㅠㅠ

2weeks0 1년 전 0

55 ~ 58번줄 없애면 통과하는데 이거 넣으면 왜 안되나요?

추가)

https://www.acmicpc.net/proble... 최소비용 구하기

위 문제와 동일하다고 생각하여 동일한 풀이로 했음에도 불구하고 본 문제만 틀리네요ㅠㅠ 이유를 도저히 모르겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(br.readLine()) - 1;
        List<Edge>[] graph = new List[v];
        for (int i = 0;i < v;i++) {
            graph[i] = new LinkedList<>();
        }
        
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int w = Integer.parseInt(st.nextToken());
            graph[a].add(new Edge(b, w));
        }

        int[] dist = dijkstra(graph, v, s);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int d : dist) {
            if (d == Integer.MAX_VALUE) {
                bw.append("INF\n");
            } else {
                bw.append(String.valueOf(d)).append('\n');
            }
        }

        bw.close();
        br.close();
    }

    static int[] dijkstra(List<Edge>[] graph, int v, int s) {
        int[] dist = new int[v];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[s] = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(i -> dist[i]));
        pq.add(s);

        boolean[] visited = new boolean[v];
        while (!pq.isEmpty()) {
            int current = pq.poll();
            
            // 55 ~ 58번줄 없애면 통과하는데 이거 넣으면 왜 안되나요?
            if (visited[current]) {
                continue;
            }
            visited[current] = true;
            
            for (Edge edge : graph[current]) {
                if (!visited[edge.to] && dist[current] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[current] + edge.weight;
                    pq.add(edge.to);
                }
            }
        }

        return dist;
    }

    static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
}

2weeks0 1년 전 0

@cksgud410 님 답변 정말 감사합니다.

답변 중 이해되지 않는 부분이 있어 댓글 남깁니다.

다익스트라에서 pq에서 poll된 node는 이미 최선의 해를 찾았다는 뜻 아닌가요?

그렇다는 것은 탐색을 더 진행해도 더 작은 가중치 값을 찾을 수 없지 않나요?

cksgud410 1년 전 0

제가 달았던 답변은 틀린게 맞습니다.ㅠ^ㅠ

답변을 작성할 당시 다익스트라 알고리즘을 생각할 때 DFS(깊이우선방식)처럼 진행되는 것처럼 머릿속으로 생각해서 도출한 결과로

제 답변은 틀린것입니다.

그래서 왜 틀린지 여러가지 상황과 테스트 케이스를 만들어보면서 확인해보았지만 저도 왜 답이 틀렸다고 나왔는지 찾지 못하였습니다.

혹시 틀린 이유를 알게되시면 댓글에 공유좀 해주시면 감사하겠습니다.

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

문제

문제

출처

ICPC

[JAVA] 다익스트라 틀린 이유 좀 봐주세요 ㅠㅠ

2weeks0 1년 전 0

2weeks0 1년 전 0

cksgud410 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말