백준 문제풀이

[Baekjoon 1753] 최단경로 - JAVA

planting grass 2023. 6. 9. 09:51
728x90

[Gold IV] 최단경로 - 1753

문제 링크

성능 요약

메모리: 133736 KB, 시간: 1132 ms

분류

데이크스트라, 그래프 이론

문제 설명

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

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

문제 풀이

해당 문제는 한 정점에서 주변 정점까지 도달하는 최단거리를 구하는 다익스트라 알고리즘이다.

다익스트라 알고리즘은 아래와 같은 순서를 가진다.

  1. 모든 정점을 미방문 상태로 표시
  2. 모든 정점에 거리값 부여
  3. 현재 정점에서 미방문 정점의 거리를 현재 정점에서 계산하여 갱신
  4. 갱신된 거리값을 기준으로 최단 거리가 가장 짧은 정점을 선택
  5. 선택된 정점을 방문한 상태로 표시
  6. 선택된 정점과 연결된 정점들의 거리를 갱신
  7. 모든 정점을 방문할 때까지 4-6단계를 반복
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.stream.Stream;

class Edge implements Comparable<Edge> {
    int node, weight;

    public Edge(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return this.weight - o.weight;
    }
}

public class q1753 {
    static ArrayList<Edge> adjacencyList[];
    static int distance[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int numberOfVertices = input[0], numberOfEdges = input[1];
        int startNode = Integer.parseInt(br.readLine());

        adjacencyList = new ArrayList[numberOfVertices + 1];
        for (int i = 1; i <= numberOfVertices; i++)
            adjacencyList[i] = new ArrayList<Edge>();
        for (int i = 0; i < numberOfEdges; i++) {
            String[] edgeInfo = br.readLine().split(" ");
            int nodeA = Integer.parseInt(edgeInfo[0]);
            int nodeB = Integer.parseInt(edgeInfo[1]);
            int weight = Integer.parseInt(edgeInfo[2]);
            adjacencyList[nodeA].add(new Edge(nodeB, weight));
        }

        distance = new int[numberOfVertices + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[startNode] = 0;

        dijkstra(startNode);

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

    private static void dijkstra(int startNode) {
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>();
        priorityQueue.add(new Edge(startNode, 0));

        while (!priorityQueue.isEmpty()) {
            Edge current = priorityQueue.poll();
            for (Edge neighbor : adjacencyList[current.node]) {
                if (distance[neighbor.node] > current.weight + neighbor.weight) {
                    distance[neighbor.node] = current.weight + neighbor.weight;
                    priorityQueue.add(new Edge(neighbor.node, distance[neighbor.node]));
                }
            }
        }
    }
}

코드 풀이

class Edge implements Comparable<Edge> {
    int node, weight;

    public Edge(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return this.weight - o.weight;
    }
}
  • Edge 클래스는 간선(Edge)을 나타내는 클래스다.
  • 각 간선은 연결된 노드와 가중치(weight)를 가지며, Comparable 인터페이스를 구현하여 우선순위 큐(PriorityQueue)에서 정렬에 사용된다.
public class q1753 {
    static ArrayList<Edge> adjacencyList[];
    static int distance[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int numberOfVertices = input[0], numberOfEdges = input[1];
        int startNode = Integer.parseInt(br.readLine());
  • 입력을 받고, 변수를 초기화하는 부분이다.
  • BufferedReader를 사용하여 표준 입력에서 값을 읽어오고, 공백을 기준으로 나누어 정수 배열로 변환한다.
  • numberOfVertices 변수는 정점의 개수를, numberOfEdges 변수는 간선의 개수를 나타낸다.
  • startNode 변수는 시작 노드를 나타낸다.
        adjacencyList = new ArrayList[numberOfVertices + 1];
        for (int i = 1; i <= numberOfVertices; i++)
            adjacencyList[i] = new ArrayList<Edge>();
        for (int i = 0; i < numberOfEdges; i++) {
            String[] edgeInfo = br.readLine().split(" ");
            int nodeA = Integer.parseInt(edgeInfo[0]);
            int nodeB = Integer.parseInt(edgeInfo[1]);
            int weight = Integer.parseInt(edgeInfo[2]);
            adjacencyList[nodeA].add(new Edge(nodeB, weight));
        }
  • adjacencyList는 인접 리스트로서, 각 정점마다 연결된 간선 정보를 저장한다.
  • numberOfVertices + 1 크기의 ArrayList 배열을 생성하고, 각 정점에 해당하는 인덱스에 빈 ArrayList를 할당한다.
  • 간선 정보를 입력받아 인접 리스트에 추가한다.
        distance = new int[numberOfVertices + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[startNode] = 0;
  • distance 배열은 시작 노드에서 각 정점까지의 최단 거리를 저장하는 배열이다.
  • 배열을 초기화하고, 시작 노드부터 자기 자신까지의 거리는 0으로 설정한다.
        dijkstra(startNode);

        for (int i = 1; i <= numberOfVertices; i++) {
            if (distance[i] == Integer.MAX_VALUE)
                System.out.println("INF");
            else
                System.out.println(distance[i]);
        }
    }
  • dijkstra 메소드를 호출하여 최단 거리를 계산하고, 결과를 출력한다.
    private static void dijkstra(int startNode) {
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>();
        priorityQueue.add(new Edge(startNode, 0));

        while (!priorityQueue.isEmpty()) {
            Edge current = priorityQueue.poll();
            for (Edge neighbor : adjacencyList[current.node]) {
                if (distance[neighbor.node] > current.weight + neighbor.weight) {
                    distance[neighbor.node] = current.weight + neighbor.weight;
                    priorityQueue.add(new Edge(neighbor.node, distance[neighbor.node]));
                }
            }
        }
    }
}
  • dijkstra 메소드는 다익스트라 알고리즘을 구현한 부분이다.
  • 우선순위 큐(priorityQueue)를 사용하여 최소 가중치를 가지는 간선을 선택하고, 해당 간선을 통해 인접한 정점까지의 거리를 갱신한다.
  • 반복적으로 이 과정을 수행하여 시작 노드부터 모든 정점까지의 최단 거리를 계산한다.
728x90
저작자표시