[BOJ] 1753. 최단경로

https://www.acmicpc.net/problem/1753

접근 방법

전형적인 다익스트라 알고리즘을 쓰는 문제이다.

가중치가 있는 Graph이기 때문!

주의할 점

그래프를 그릴 때 이중배열로 받게 되면 메모리 초과가 나기 때문에

이중리스트그래프로 받자

Need Know

1. 다익스트라 알고리즘

전체 코드 ( Java )

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static int V; // Vertex
    static int E; // Edge
    static int K; // 출발점
    static ArrayList<Location>[] map;
    static PriorityQueue<Location> pq;
    static int[] distance;

    public static void main(String[] args) throws IOException {
        set();
        solve();
        System.out.print(sb);
        br.close();
    }

    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
        pq = new PriorityQueue<>();
        distance = new int[V+1];
        map = new ArrayList[V+1];
        for(int i=1; i<V+1; i++){
            map[i] = new ArrayList<>();
        }
        for(int i=1; i<V+1; i++){
            distance[i] = Integer.MAX_VALUE;
        }
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            map[u].add(new Location(v,w));
        }
        pq.offer(new Location(K,0));
    }

    static void solve() throws IOException {
        bfs();
        distance[K] = 0;
        for(int i=1; i<V+1; i++){
            String dist = distance[i] == Integer.MAX_VALUE ? "INF" : String.valueOf(distance[i]);
            sb.append(dist + "\n");
        }
    }
    static void bfs(){
        while(!pq.isEmpty()){
            Location nowLoc = pq.poll();
//            System.out.println("nowLoc : " + nowLoc.x);
            for(int i=0; i<map[nowLoc.x].size(); i++){
//                System.out.println("check : " +  map[nowLoc.x].get(i).x);
                    int nextDist = nowLoc.distance + map[nowLoc.x].get(i).distance;
                    if(distance[ map[nowLoc.x].get(i).x ] > nextDist){
                        distance[  map[nowLoc.x].get(i).x ] = nextDist;
                        pq.offer(new Location( map[nowLoc.x].get(i).x ,nextDist));
                    }
                }
            }
        }
    }

class Location implements Comparable<Location>{
    int x,distance;

    public Location(int x, int distance) {
        this.x = x;
        this.distance = distance;
    }

    @Override
    public int compareTo(Location o) {
        return distance-o.distance;
    }
}