[백준 / 골드 4] 1753 최단경로 (Java)

문제 보기

사용한 것

• 그래프의 한 정점에서 다른 정점까지의 최단 거리를 구하기 위한 다익스트라
• 간선의 정보를 담기 위한 Edge

풀이 방법

• Edge 리스트를 값으로 가지고 있는 리스트인 graph를 선언하고 초기화 해준다.
• 간선을 입력 받으면서 graph에 저장한다.
• visited와 dist를 선언하고 dist의 입력 받은 start 인덱스에 0을 입력한다. (자기 자신의 거리는 0이므로)
• 정점은 총 V개 이므로 V번 반복문을 실행한다.
• 방문하지 않은 인덱스 중 현재 가장 작은 dist를 가지고 있는 인덱스를 선택한다.
• 선택 후 visited의 해당 인덱스를 true로 바꾼다.
• 해당 인덱스 정점이 가지고 있는 Edge들의 to 인덱스 정점들 중, 현재의 dist보다 현재 정점의 cost와 Edge의 cost를 더한 값이 더 작으면 교체한다.
• 모든 정점을 돌면서 처음 설정한 dist 값인 int 최대 값이면 도달할 수 없는 경우 이므로 "INF"를 출력하고 아닌 경우에는 dist의 해당 인덱스를 출력한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int V = Integer.parseInt(line[0]);
        int E = Integer.parseInt(line[1]);
        int start = Integer.parseInt(br.readLine());
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < E; i++) {
            line = br.readLine().split(" ");
            int from = Integer.parseInt(line[0]);
            int to = Integer.parseInt(line[1]);
            int cost = Integer.parseInt(line[2]);
            graph.get(from).add(new Edge(to, cost));

        }

        boolean[] visited = new boolean[V + 1];
        int[] dist = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[start] = 0;

        for (int i = 0; i < V; i++) {
            int idx = 0;
            int cost = Integer.MAX_VALUE;
            for (int j = 1; j <= V; j++) {
                if (!visited[j] && dist[j] < cost) {
                    cost = dist[j];
                    idx = j;
                }
            }

            visited[idx] = true;

            List<Edge> edges = graph.get(idx);
            for (int j = 0; j < edges.size(); j++) {
                Edge edge = edges.get(j);
                dist[edge.to] = Math.min(cost + edge.cost, dist[edge.to]);
            }
        }

        for (int i = 1; i <= V; i++) {
            if (dist[i] != Integer.MAX_VALUE) {
                System.out.println(dist[i]);
            } else {
                System.out.println("INF");
            }
        }
    }
}

class Edge {

    int to;
    int cost;

    public Edge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}