글 읽기 - java 20%에서 틀렸다고 합니다... 어디가 문제인가요???

paulus0617 2년 전 0

이전에 짰던 다익스트라 코드와 비교해봐도 뭐가 틀린지 모르겠네요...

질문 게시판에 있는 반례까지 다 해봤는데 정상으로 나옵니다ㅜㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

  /**
   * 방향성이 있고, 가중치가 있다 -> 다익스트라로 풀자
   */

  static int n, m;
  static ArrayList<int[]>[] road;
  static int[] pay; // 해당 정류장으로 가는 최소 비용이 담긴 배열


  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    m = Integer.parseInt(br.readLine());
    road = new ArrayList[n+1]; // 리스트형을 자료형으로 가지는 배열
    for(int i = 0; i < road.length; i++){
      road[i] = new ArrayList<>(); // 초기화
    }
    pay = new int[n+1];
    Arrays.fill(pay, Integer.MAX_VALUE); // 최댓값을 넣고 시작

    StringTokenizer st;
    for(int i = 0; i < m; i++){
      st = new StringTokenizer(br.readLine());
      int s = Integer.parseInt(st.nextToken());
      int e = Integer.parseInt(st.nextToken());
      int dist = Integer.parseInt(st.nextToken());
      road[s].add(new int[] {e, dist}); // 배열의 인덱스는 출발점, 각 인덱스에 도착점과 비용 삽입
    }
    st = new StringTokenizer(br.readLine());
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());

    // dijkstra
    Queue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o1[1] - o2[1];
      }
    }); // 우선순위큐 : 비용이 작은 것부터 탐색
    boolean[] visited = new boolean[n+1]; // 방문여부 검사
    pq.add(new int[] {start, 0}); // add start point
    pay[start] = 0;
    while(!pq.isEmpty()){
      int[] cur = pq.poll();
      // 방문하지 않은 곳에 대해서만 추가
      if(!visited[cur[0]]){
        visited[cur[0]] = true;

        for(int[] i : road[cur[0]]){
          if(pay[i[0]] > pay[cur[0]] + i[1]){
            pay[i[0]] = pay[cur[0]] + i[1];
            pq.add(i);
          }
        }
      }
    }
    System.out.println(pay[end]);
  }
}

paulus0617 2년 전 0

다익스트라 알고리즘에서 우선순위큐에 새로운 데이터를 삽입할 때

해당 칸으로 가는 최소 비용을 삽입해야 되는군요...

59번 줄에 pq.add(i);

이 부분을

pq.add(new int[] {i[0], pay[i[0]]})

이렇게 바꾸니 정상적으로 돌아갑니다.

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

문제

문제

출처

ICPC

java 20%에서 틀렸다고 합니다... 어디가 문제인가요???

paulus0617 2년 전 0

paulus0617 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말