[BOJ/백준] 최단경로 (Dijkstra)

백준 1753: 최단경로
- 풀이
- 정답 코드 (Dijkstra)
마무리

이번에 소개해드릴 문제는 다익스트라 알고리즘을 이용하여 그래프 내에서 최단 경로를 구하는 문제입니다. 예전에는 곧잘 풀곤했는데, 지금은 예전의 제 코드를 보면서 다시한번 풀어보았습니다.

백준 1753: 최단경로

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

풀이

최단경로를 구하는 알고리즘 중 가장 일반적으로 사용하면서 그래프 내에 음의 가중치가 없는 경우 사용할 수 있는 다익스트라 알고리즘을 사용해볼 수 있는 문제입니다.

정답 코드 (Dijkstra)

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

public class Boj1753 {
    private static int INF = Integer.MAX_VALUE;
    private static int V; // 노드 수
    private static int E; // 엣지 수
    private static List<Edge>[] graph = new ArrayList[20001]; // 그래프 정보
    private static int[] distance = new int[20001]; // 거리 정보
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] ins = br.readLine().split(" ");
        V = Integer.parseInt(ins[0]);
        E = Integer.parseInt(ins[1]);

        int s = Integer.parseInt(br.readLine());

        for (int i = 0; i < 20001; i++) {
            graph[i] = new ArrayList<>();
            distance[i] = INF;
        }

        distance[s] = 0;

        Map<Integer, List<Edge>> edges = new HashMap<>();

        for (int i = 0; i < E; i++) {
            ins = br.readLine().split(" ");
            int u = Integer.parseInt(ins[0]);
            int v = Integer.parseInt(ins[1]);
            int w = Integer.parseInt(ins[2]);

            graph[u].add(new Edge(v, w));
        }

        dijkstra(s);
        bw.write(print());
        bw.flush();
        bw.close();
    }

    private static String print() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            sb.append((distance[i] == INF ? "INF": distance[i]));
            sb.append("\n");
        }
        return sb.toString();
    }

    private static void dijkstra(int s) {
        // 다익스트라의 경우, 성능을 위해 우선순위 큐를 사용
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(s, distance[s]));

        // 방문한 노드인지 체크하는 배열, 
        // 우선순위 큐를 사용할 때만 해당 배열을 사용 가능
        // 일반 큐의 경우 같은 노드를 여러 번 방문해야 최소값을 찾을 수 있음
        boolean[] visited = new boolean[20001];

        while (!pq.isEmpty()) {
            
            Edge e = pq.poll();

            // 해당 노드 방문 체크
            // 이 노드는 우선 순위 큐로 방문되어 이미 최소값이 결정되어 있음
            visited[e.v] = true;

            for (int i = 0; i < graph[e.v].size(); i++) {
                int from = e.v; // 현재 노드
                int to = graph[e.v].get(i).v; // 현재 노드와 연결된 노드
                int weight = graph[e.v].get(i).w; // 연결된 노드와의 가중치

                // 연결된 노드가 처음 방문하는 노드 이면서
                // 이미 저장된 연결된 노드까지의 거리 > 현재 노드 + 현재 ~ 연결된 노드의 가중치인 경우, 거리 갱신
                if (!visited[to] && distance[to] > distance[from] + weight) {
                    distance[to] = distance[from] + weight;
                    pq.offer(new Edge(to, distance[to]));
                }
            }
        }
    }

    private static class Edge implements Comparable<Edge> {
        private int v;
        private int w;

        public Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.w, o.w);
        }
    }
}

마무리

그래프 문제가 그렇게 많이 출제지는 않는 것 같지만, 출제된다면 그래프 문제의 기본이 되는 다익스트라 알고리즘은 익숙하게 다룰줄 알아야한다고 생각합니다. 혹시 궁금하신 점이나 이상한 점이 있다면 댓글 부탁드리겠습니다.

감사합니다.

#능력 회복하기,
#백준,
#백준 1753,
#알고리즘,
#최단경로

글이 도움이 되셨다면, 커피 한 잔만 사주세요!

Comments

Copied to clipboard

[BOJ/백준] 최단경로 (Dijkstra)

Table of Contents

백준 1753: 최단경로

풀이

정답 코드 (Dijkstra)

마무리