[백준 11779] 최소비용 구하기 2 ( 다익스트라 )

문제 요약 

n개의 도시가 있을 때 출발지에서 도착지까지 가는 최소 비용과 경로를 출력해야하는 문제. 

문제 입출력

첫째 줄에 도시의 개수 n 이 주어짐

둘째줄에 버스의 개수 m이 주어짐

셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어짐

마지막줄에 출발 도시의 번호와 도착지의 도시 번호가 주어짐

입력 제한 크기

n(1≤n≤1,000)

m(1≤m≤100,000)

접근 아이디어

기본 다익스트라의 경우 특정 출발지로부터 모든 노드까지의 최소비용을 구할 뿐, 경로를 구하지 않는다.

따라서 경로를 저장하는 배열을 만들어 경로가 업데이트 될 때 마다 변경해 준다.

코드

import java.awt.Point;
import java.util.*;
import java.io.*;

public class b11779 {
  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int n, m;
    int start, end ;
    n = Integer.parseInt(br.readLine());
    m = Integer.parseInt(br.readLine());
    int[][] graph = new int[n + 1][n + 1];
    boolean [] visited = new boolean [n+1];
    int [] dp = new int [n+1];
    
    // 최단 경로와, 경로까지의 거리를 저장하는 배열
    String [] path = new String[n+1];
    int [] cnt = new int[n+1];

    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= n; j++) {
        if (i==j)
          graph[i][j] = 0;
        else
          graph[i][j] = 1000000001;
      }
    }

    for(int i=0; i<m ; i++){
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      if (a==b)
        continue;
      int cost = Integer.parseInt(st.nextToken());
      graph[a][b] = Math.min(cost, graph[a][b] );
    }
    st = new StringTokenizer(br.readLine());

    start = Integer.parseInt(st.nextToken());
    end = Integer.parseInt(st.nextToken());

    for(int i= 0; i<= n ; i++){
      path[i] = start + " " + i;
      dp[i] = 1000000001;
      cnt[i] = 2;
    }
    cnt[start] = 1;
    path[start] = start +"";
    
    /* -------------- 다익스트라 시작 ----------------- */
    for(int i=1; i<=n; i++){
      dp[i] = graph[start][i];
    }
    visited[start] = true;

    for(int i = 1; i<n; i++) {
      int minVal = Integer.MAX_VALUE;
      int minIdx = 0;
      for (int j = 1; j <= n; j++) {
        if (!visited[j] && minVal > dp[j]) {
          minVal = dp[j];
          minIdx = j;
        }
      }
      visited[minIdx] = true;
      for (int j = 1; j <= n; j++) {
        if(j==minIdx)
          continue;
        if (dp[j] > dp[minIdx] + graph[minIdx][j] ) {
          dp[j] = dp[minIdx] + graph[minIdx][j];
          path[j] = path[minIdx]  + " " + j;
          cnt[j] = cnt[minIdx] + 1;
        }
      }
    }
    System.out.println(dp[end]);
    System.out.println(cnt[end]);
    System.out.println(path[end]);
  }
}

 

참고할 만한 점

코테에 간간히 나오는 다익스트라 문제 

다익스트라 구현법을 익혀두자..

다익스트라 순서

1. 출발지로부터 각 노드의 거리를 저장한다. (못가는 경우 INF)

2. 방문하지 않은 노드 중 출발지로부터 가장 거리가 짧은 노드를 선택한다.

• 출발지 -> 선택된 노드 -> 다음 노드 
• dp[ 다음 노드 ] = Math.min(dp[다음 노드 ], dp[선택된노드] + graph[선택된노드 ][다음 노드]) 
• 이렇게 모든 노드들의 거리를 갱신해 준다.
• 이후 선택된 노드의 visited를 체크해준다.

3. 2의 과정을 반복하여 모든 노드를 거쳐가는 경우를 다 계산한 뒤 마무리