문제

최소비용 구하기

풀이

다익스트라 문제이다. BFS와 헷갈리지만 다른 점은 있다. BFS는 모든 간선의 가중치가 같지만 다익스트라는 다르다는 점이다.

1. 시작점에서 출발했을때 각지점에 도달할 가장 짧은 비용을 담을 배열을 선언한다

		int[] costs = new int[n + 1];
        Arrays.fill(costs, Integer.MAX_VALUE);

배열은 1부터 시작하기 때문에 n+1까지 생성하고 배열 안에 가장 큰 수를 입력한다.

2. 다익스트라는 가장 최소비용으로 큐를 add하기 위해서는 PriorityQueue를 사용한다. 이렇게 하기 위해서는 Compareable또는 Comparator를 사용하면 된다

	static class City implements Comparable<City> {
        int next;
        int cost;

        City(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }

        @Override
        public int compareTo(City o) {
            return this.cost - o.cost;
        }
    }

3. BFS처럼 코드를 생성하는데, 큐로 입력하는 순간 방문 처리하는 것이 아니라 큐로 갈수 있는 정보들을 전부 넣고 난 다음 정렬된 PriorityQueue의 성질을 사용하여 가장 짧은 부분 먼저 접근한다.

		PriorityQueue<City> q = new PriorityQueue<>();
        q.add(new City(start, 0));
        costs[start] = 0;
        while (!q.isEmpty()) {
            City city = q.poll();
            if (!visit[city.next]) {
                visit[city.next] = true;
                for (City c : arr[city.next]) {
                    if (!visit[c.next] && costs[city.next] + c.cost < costs[c.next]) {
                        costs[c.next] = costs[city.next] + c.cost;
                        q.add(new City(c.next, costs[c.next]));
                    }
                }
            }
        }

전체 코드

전체 코드