[백준] 1916 : 최소비용 구하기 (JAVA/자바)

문제

BOJ 1916 : 최소비용 구하기 - https://www.acmicpc.net/problem/1916

풀이

A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키는게 목적이기 때문에, A가 출발지가 되어 다른 도시까지의 최소 경로를 구해야 한다. Dijkstra Algorithm을 사용한다.

<다익스트라 알고리즘 구현>

1. A를 시작점으로 했을 때의 다른 도시까지의 거리에 대한 정보를 dist[]로 선언하여 초기화한다. 가는 길이 존재한다면 해당 weight를, 경로가 존재하지 않으면 무한대(Integer.MAX_VALUE-1) 값으로 초기화한다.
2. 다른 도시를 방문했는지 여부를 체크하기 위해 visited[]를 선언한다.
3. 시작점을 제외하고 dist[]의 값이 가장 작은 도시의 index를 가져온다.
4. 해당 index를 visited 처리 한 뒤, 그 index의 도시를 거쳐가는 경로가 원래 dist[]에 들어있는 값보다 작으면 값을 변경한다.
5. 3~4번을 n-1번 반복한다.

dist에서 B에 해당하는 index 값을 print하고 종료한다.

코드

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

public class Main {

    static long[] dist;
    static boolean[] visited;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        int[][] map = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(i==j) {
                    map[i][j] = 0;
                    continue;
                }
                map[i][j] = Integer.MAX_VALUE-1; // infinite
            }
        }

        for (int i = 0; i < m; i++) {
            String[] inputs = br.readLine().split(" ");
            int s = Integer.parseInt(inputs[0]);
            int e = Integer.parseInt(inputs[1]);
            int w = Integer.parseInt(inputs[2]);

            // 같은 경로가 여러 번 들어올 경우 가장 작은 weight 값을 저장
            if(map[s][e] == -1)
                map[s][e] = w;
            else if(map[s][e] > w)
                map[s][e] = w;

        }

        String[] inputs = br.readLine().split(" ");
        int start = Integer.parseInt(inputs[0]);
        int end = Integer.parseInt(inputs[1]);


        dist = new long[n + 1];
        visited = new boolean[n + 1];

        // Dijkstra

        // distance initialize
        for (int i = 1; i <= n; i++) {
            dist[i] = map[start][i];
        }

        visited[start] = true;

        for (int i = 0; i < n - 1; i++) {
            int cur = getMinIdx();
            visited[cur] = true;
            for (int j = 1; j <= n; j++) {
                if(!visited[j]){
                    if (dist[cur] + map[cur][j] < dist[j]) { // 거쳐가는게 더 빠르면 갱신
                        dist[j] = dist[cur] + map[cur][j];
                    }
                }
            }
        }

        System.out.println(dist[end]);

    }

    public static int getMinIdx() {
        long min = Integer.MAX_VALUE;
        int idx = 0;

        for (int i = 1; i <= n; i++) {
            if (dist[i] < min && !visited[i]) {
                min = dist[i];
                idx = i;
            }
        }
        return idx;
    }

}

정리

✔ 알고리즘 분류 - 그래프 이론, 다익스트라
✔ 난이도 - 🟡 Gold 5

🤦‍♀️ 오늘의 메모

• 처음엔 MST 문제인줄 알고 풀었다가 처음부터 다시 풀었다. 문제 대충읽지 말고 로직부터 생각해 제발..
• 다익스트라 개념을 오랜만에 봤더니 굉장히 생소한 느낌이었다. 이번 기회에 잘 알아둘 것!

참고 사이트

https://blog.naver.com/PostView.naver?blogId=ndb796&logNo=221234424646&redirect=Dlog&widgetTypeCall=true&directAccess=false (Dijkstra Algorithm)