[백준] no1916: 최소비용 구하기 - 우선순위큐 다익스트라

문제

Input

첫 번째 줄 : 도시(노드)의 수 N
두 번째 줄 : 버스(간선)의 수 M
세 번째 ~ M+2번째 줄 : 출발지점 도착지점 비용
마지막 줄 : 출발지점A 도착지점B

Output

A에서 B로가는 최소비용

문제 링크 : https://www.acmicpc.net/problem/1916

---

원리

1. 노선이 없는 경우(null)를 확인하기위해 Integer[][]사용

private static Integer[][] map;

2. 버스 노선별 비용 입력시, 비용 최소화

if(map[start][end] != null) map[start][end] =  Math.min(map[start][end], cost);
else map[start][end] = cost;

3. BFS 탐색시, 비용 합산이 적은 경우를 우선적으로 처리하기위해 우선순위큐 사용

private static void BFS() {
    PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.cost - b.cost);
    ...   
}

4. 탐색중 이동경로가 일부 겹쳐서, 최단경로가 나오지 못하는 경우를 방지하기 위해 이차원 배열 visit 사용

    private static boolean[][] visit; // 중간 경유지마다 출발/도착 city가 다르므로, 일차원 배열로는 방문체크가 안됨

---

나의 코드

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, M, A, B, result;
    private static Integer[][] map;
    private static boolean[][] visit; // 중간 경유지마다 출발/도착 city가 다르므로, 일차원 배열로는 방문체크가 안됨

    public static void main(String[] args) throws IOException {
        // 초기 입력 단계
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        map = new Integer[N+1][N+1];
        StringTokenizer st;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            if(map[start][end] != null) map[start][end] =  Math.min(map[start][end], cost);
            else map[start][end] = cost;
        }

        st = new StringTokenizer(br.readLine(), " ");
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        BFS(); // 실질적인 탐색 구간

        System.out.println(result);
    }

    private static void BFS() {
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.cost - b.cost);
        visit = new boolean[N+1][N+1];
        pq.add(new Node(A, 0));

        while(!pq.isEmpty()) {
            Node now = pq.poll();

            if(now.city == B) {
                result = now.cost;
                break;
            }

            for(int next = 1; next <= N; next++) {
                if(!visit[now.city][next] && map[now.city][next]!=null) {
                    pq.add(new Node(next, map[now.city][next] + now.cost));
                    visit[now.city][next] = true;
                }
            }
        }
    }

    private static class Node {
        private int city, cost;
        public Node(int city, int cost) {
            this.city = city;
            this.cost = cost;
        }
    }

 

---

레퍼런스

참고링크 : https://steady-coding.tistory.com/84

(일반적으로 우선순위 큐를 이용한 다익스트라로 해결하나보다)