문제 탐색하기

입력 자료 정리

1. n은 노드의 개수, m은 간선의 개수다
2. 이어서 들어오는 값은 차례대로 출발지, 도착지, 비용이다
3. 마지막은 탐색하고자 하는 시작지점과 도착지점이다

해결방법 추론

1. 노드와 간선이 존재하면서, 간선에 가중치가 있고,
   이때 최소비용 즉, 최단거리를 구하는 조건이 주어졌다면 간단하게 최단거리 알고리즘을
   사용하면 해결할 수 있겠다고 생각할 수 있다
2. 이때 주어진 비용이 음의 가중치를 가지고 있지 않고 있기 때문에,
   다익스트라 알고리즘으로 해결할 수 있음을 알 수 있다
3. 다익스트라 알고리즘을 이용해 시작지점에서 출발해서 모든 노드로 이동하는 최단거리를 구한다음
   도착지점의 최단거리를 출력한다면 쉽게 문제를 해결할 수 있을 것이다

시간복잡도 계산

1. 다익스트라 알고리즘을 우선순위 큐를 이용해 해결한다면 mlogm의 연산이 발생한다
2. 따라서 시간복잡도는 O(mlogm)이 된다
3. 이때 m의 최대값은 10만이므로, logm의 밑이 10이라 가정했을 때 5가 되므로
   전체 연산은 50만이 될 것이고 시간 제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. n과 m은 int형 변수로 관리하며, 리스트 배열을 이용하여 간선간의 연결을 관리한다
2. 이때 Node타입의 클래스를 만들어 도착지점의 간선과 비용을 함께 관리하도록 한다
3. 이어서 들어오는 간선의 정보는 a,b,c로 나누어 관리하고,
   a를 출발지, b를 도착지, c를 비용으로 관리하여 리스트 배열에 저장한다
4. 마지막 입력인 출발지와 도착지 정보를 입력받아 변수로 관리한다

다익스트라 설계

1. 다익스트라를 위해 선행 배열을 만들어둔다
2. 먼저 각 노드별 최단거리를 관리할 dist 배열을 int형 1차원배열로 선언하고,
   방문 체크를 위한 boolean형 1차원 배열도 선언한다. 둘다 n+1의 크기를 갖는다
3. 최단거리 갱신을 위해 dist 배열은 Integer.MAX_VALUE로 초기화해둔다
4. 다익스트라 알고리즘을 돌릴 메소드를 설계한다.
   파라미터로는 노드의 개수인 n과 시작지점, 도착지점을 갖는다
5. 우선순위 큐를 Node 클래스 타입으로 하여 선언한다.
   이때, 정렬은 Node 클래스의 cost (비용)필드를 기준으로 오름차순 정렬한다
6. dist의 출발지점 인덱스는 0으로 초기화하고 비용을 0으로 하여 시작지점을
   우선순위 큐에 넣는다
7. 이어서 우선순위 큐가 비어있지 않는 동안 탐색을 반복한다
8. 미방문 배열에 대해, 방문 체크를하고, 연결된 모든 노드를 탐색한다
9. 만약 연결된 노드의 dist가 현재 지점의 dist 비용과 연결된 노드의 비용을 더한값보다 크다면,
   값을 갱신하고 우선순위 큐에 그 갱신된 값을 넣어준다
10. 모든 다익스트라 알고리즘의 탐색이 끝난 뒤, 도착지점의 dist를 ans에 넣어준다

출력 설계

1. ans는 정답 출력을 위해 선언한 int형 변수다
2. 완성한 ans를 그대로 출력하면 정답이 된다.

정답 코드

(1회차 시도 성공)

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


class Node{
    int end;
    int cost;

    public Node(int end, int cost) {
        this.end = end;
        this.cost = cost;
    }
}


public class Main {

    static List<Node>[] lists;
    static int[] dist;
    static boolean[] visited;
    static int ans = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        lists = new ArrayList[n+1];
        for (int i = 0; i < n + 1; i++) {
            lists[i] = new ArrayList<>();
        }
        dist = new int[n+1];
        visited = new boolean[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            lists[a].add(new Node(b, c));
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        dijkstra(n, start, end);
        bw.write(ans+"");

        br.close();
        bw.close();
    }

    private static void dijkstra(int n, int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
            return o1.cost - o2.cost;
        });
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()) {
            Node now = pq.poll();
            if(!visited[now.end]){
                visited[now.end] = true;
                for (Node node : lists[now.end]) {
                    if(dist[node.end] > dist[now.end] + node.cost){
                        dist[node.end] = dist[now.end] + node.cost;
                        pq.add(new Node(node.end, dist[node.end]));
                    }
                }
            }
        }

        ans = dist[end];

    }

}

문제 링크

1916 - 최소비용 구하기