백준 1916번 (java)

백준 1916번 최소비용 구하기

---

관찰

1. 완전 탐색 - 다익스트라를 활용해서 전체 배열을 큰 수로 채운 후 최소거리를 갱신하면서 전부 다 탐색한다! 풀어보자!

실패코드

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

public class Main {
    static class Rode{
        int to;
        int weight;
        public Rode(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    static int n; // 도시의 갯수 1000
    static int m; // 버스의 갯수 100000
    static List<Rode>[] pList; // 인접리스트 그래프
    static int[] dist; // 다익스트라를 위한 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        pList = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            pList[i] = new ArrayList<Rode>();
        }
        dist = new int[n+1];

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            pList[a].add(new Rode(b, c));
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

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


    }

    private static void bfs(int start) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        Queue<Integer> q = new LinkedList<Integer>();
        dist[start] = 0;
        q.add(start);
        while(!q.isEmpty()){
            int cur = q.poll();
            for(Rode next : pList[cur]){
                if(next.weight + dist[cur] > dist[next.to]) continue;
                dist[next.to] = next.weight + dist[cur];
                q.add(next.to);
            }
        }
    }
}

visited 없이 모든 간선을 bfs를 전부다 돌리니 당연히 시간 초과가 발생한다..

---

2. 완전탐색을 하는 것이 아닌 우선순위 큐를 활용하여 몇번 이동했는지는 상관하지 않고 가장 가중치의 합이 작은 길을 택하여 탐색한다! 그러면 완전탐색이 아닌 모든 노드를 한번씩 방문하면 탐색이 끝난다!

정답 코드

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

public class Main{
    static class Rode implements Comparable<Rode> {
        int to;
        int weight;
        public Rode(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Rode o) {
            return this.weight - o.weight;
        }
    }
    static int n; // 도시의 갯수 1000
    static int m; // 버스의 갯수 100000
    static List<Rode>[] pList; // 인접리스트 그래프
    static int[] dist; // 다익스트라를 위한 배열
    static int start,end; //출발과 끝
    static int[] visited; // 방문관리
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        pList = new ArrayList[n+1];
        for(int i = 0; i <= n; i++) {
            pList[i] = new ArrayList<Rode>();
        }

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            pList[a].add(new Rode(b, c));
        }

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        bfs(start);
        System.out.println(dist[end]);
    }

    private static void bfs(int start) {
        // 초기값 설정
        visited = new int[n+1];
        dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 탐색 시작
        PriorityQueue<Rode> pq = new PriorityQueue<>();
        pq.add(new Rode(start, 0));
        dist[start] = 0;
        while(!pq.isEmpty()) {
            Rode curRode = pq.poll();
            int cur = curRode.to;
            if(visited[cur] == 1) continue;
            visited[cur] = 1;
            for(Rode next : pList[cur]) {
                if(next.weight + dist[cur] >= dist[next.to]) continue;
                dist[next.to] = next.weight + dist[cur];
                pq.add(new Rode(next.to, dist[next.to]));
            }
        }
    }
}

---

풀이

다익스트라 변형 문제다 우선순위큐, dist 를 통해서 최적의 길을 우선으로 찾아서 탐색하는 방식으로 굉장히 빠른 시간에 가장 최소값을 찾을 수 있다.

---

느낀점

골드5라서 쉽게 풀 수 있을 줄 알았는데 2시간 넘게 걸렸다..
이 문제를 풀면서 배운 것은 우선순위 큐에 대한 강력함이다 (vs bfs)
bfs는 큐 순서가 정해져 있어 파동처럼 탐색한다
하지만 우선순위큐는 새로이 큐에 넣은 값이 가장 먼저 나올 수 있는 것이다!
순서가 보장되지 않고 내가 원하는 순서로 하나씩 탐색이 가능하다는 것!
이 특성을 더 사용할 수 있는 방식을 더 찾아봐야겠다 좋은 문제였던것 같다