056 : 최단 경로 구하기

 

단순 에지 순회만 하는 bellman-ford는

- queue 대신 Edge[] 를 사용

- Edge(s, e, w) class 공급하나 Comparable 넣지않음

 

MSP는

- PQ 사용

-  Edge class(s, e, w) 공급 및 w 기반 Comaparble 역시 사용

 

 

 

 

 

 

Topology Sort는

- ArrayList<ArrayList<Integer>>로 []접근하지 않고 V만큼 ArrayList<>() 초기화 공급

- get으로 access

 

 

DFS, BFS는

- ArrayList<Integer>[] 로 양방향 노드 더하기

 

Dijkstra는

- ArrayList<Edge>[]로 특정 노드에 연결된 '다음 노드 + distance' TP 정보를 공급

- 최단거리부터 갱신해야하므로 w 기반 PQ도 필요하다

- sP 필요

 

 

 

 

 

 

sP 작업 필요

 

에지가 여러개 있을 수 있으므로 기본적으로는 BFS를 타되, revisit 방지 위한 boolean 쌍도 필요하다 

 

현재 노드에서 다음 노드까지 거리이므로

지금노드까지 거리 + 에지길이정보 로 갱신

 

기본 Integer 아닌 공급받은 class를 사용할 때 항상 new Edge라고 명시해 줘야함

 

BFS에서 갱신된 connected를 넣을 때

 

 

 

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {

        // ISC
        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 K = Integer.parseInt(st.nextToken());

        // D2F
        ArrayList<Edge>[] TP = new ArrayList[V+1];
        for (int i = 1; i <= V; i++) {
            TP[i] = new ArrayList<>();
        }
        for (int i = 1; i <= E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            TP[s].add(new Edge(e,w));
        }

        boolean[] visited = new boolean[V+1];

        int[] D = new int[V+1];
        Arrays.fill(D, Integer.MAX_VALUE);
        D[K] = 0;

        // sP
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(K, 0));

        // OP
        while (!pq.isEmpty()) {

            Edge now = pq.poll();
            if (visited[now.v])
                continue;
            visited[now.v] = true;

            for (Edge connected : TP[now.v]) {
                if (D[connected.v] > D[now.v] + connected.w) {
                    D[connected.v] = D[now.v] + connected.w;
                    pq.add(new Edge(connected.v, D[connected.v]));
                }
            }
        }

        // OEC
        for (int i = 1; i <= V; i++) {
            if (visited[i])
                System.out.println(D[i]);
            else
                System.out.println("INF");
        }
    }
}

class Edge implements Comparable<Edge> {
    int v;
    int w;
    Edge(int v, int w) {
        this.v = v;
        this.w = w;
    }
    @Override
    public int compareTo(Edge e) {
        if (this.w > e.w)
            return 1;
        else
            return -1;
    }
}