[java]최단 경로 - 백준1753

문제

• 최단 경로(백준1753)

풀이

문제 해석을 하자면,

• 다익스트라 문제이다.

풀이

• 다익스트라로 풀면 바로 풀리는 문제이다.
• 키워드로 우선순위큐(도착점,거리) + new 거리배열 을 꼭 기억해서 풀어주자.
  • 추가로 (예외) 최단거리 배열과 현재 도착거리가 다르면 PASS 까지 함꼐 기억하자.

코드

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    int V = Integer.parseInt(stk.nextToken());
    int E = Integer.parseInt(stk.nextToken());
    int K = Integer.parseInt(br.readLine());
    List<Pair>[] graph = new ArrayList[V+1];
    for(int i=0; i<=V; i++) graph[i]=new ArrayList<>(); //init
    for(int i=0; i<E; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int u = Integer.parseInt(stk.nextToken());
        int v = Integer.parseInt(stk.nextToken());
        int w = Integer.parseInt(stk.nextToken());
        graph[u].add(new Pair(v,w)); //방향그래프
    }
    //run
    PriorityQueue<Pair> pq = new PriorityQueue<>();
    int[] dist = new int[V+1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[K] = 0; // 시작노드
    pq.offer(new Pair(K, dist[K])); // 세팅끝
    while(!pq.isEmpty()) {
        int size = pq.size();
        for(int s= 0 ; s<size; s++) {
            Pair cur = pq.poll();
            if(dist[cur.n] != cur.w) continue; // 최단거리 배열과 현재 도착거리가 다르면 PASS(예외)
            for(Pair nxt : graph[cur.n]){
                if(dist[nxt.n] <= dist[cur.n] + nxt.w) continue;
                dist[nxt.n] = dist[cur.n] + nxt.w;
                pq.offer(new Pair(nxt.n, dist[nxt.n])); // 삽입시점
            }
        }
    }
    //output
    for(int i=1; i<=V; i++){
        if(dist[i] == Integer.MAX_VALUE) sb.append("INF").append("\n");
        else sb.append(dist[i]).append("\n");
    }
    System.out.println(sb);
}

static class Pair implements Comparable<Pair> {
    int n; int w;
    public Pair(int n, int w){
        this.n=n; this.w=w;
    }

    @Override
    public int compareTo(Pair o) {
        return this.w-o.w; //asc
    }
}

느낀점

생략