[프로그래머스][Level3][Java] 배달

programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

문제풀이

처음에는 BFS로 풀면 되지 않을까? 생각하였다. 하지만 BFS로 풀게 되면 1부터 시작해서 갈 수 있는 K 시간 이하로 배달이 가능한 마을을 구분할 수가 없어서

(정점 1->3->5가 이어져 있지만 비용이 K 초과라서 못가지만 정점 1->2->3->5 K이하인 경우)  최소비용을 생각하여 다익스트라 알고리즘으로 접근하게 되었다. 

• 제한 사항에서 "두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다."를 생각하여 최소값의 간선만 가지게 2차원 map 배열을 만들어준다.
• 우선순위 큐로 비용이 작은 순으로 처리한다.  
• while문을 이용하여 도착 정점까지 최소값을 갱신한다.
  
  1. 방문하지 않은 정점들 중에 출발지에서 자신까지 오는 비용이 최단인 정점을 고려할 경유지로 선택
  2. 선택된 current 정점을 경유지로 해서 아직 방문하지 않은 다른 정점으로의 최단거리 비용 계산하여 유리하면 update
• for문으로 도착 정점을 다르게 하여 if(distance[end]<=K) 이면 갈 수 있기 때문에 answer를 증가해준다.

코드

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int solution(int N, int[][] road, int K) {
		int answer = 1;
		int start = 1;
		int[][] map = new int[N + 1][N + 1];
		
		for (int i = 0; i < road.length; i++) {
        	// 정점들 간데 중복 간선이 존재할 때 최소값만 가지게 한다.
			if (map[road[i][0]][road[i][1]] > 0) {
				map[road[i][0]][road[i][1]] = Math.min(map[road[i][0]][road[i][1]], road[i][2]);
				map[road[i][1]][road[i][0]] = map[road[i][0]][road[i][1]];
			} else {
				map[road[i][0]][road[i][1]] = road[i][2];
				map[road[i][1]][road[i][0]] = road[i][2];
			}
		}

		for (int i = 2; i <= N; i++) {
			int[] distance = new int[N + 1];
			boolean[] visited = new boolean[N + 1];
			int end = i;
			PriorityQueue<Vertex> pQueue = new PriorityQueue<Vertex>();

			Arrays.fill(distance, Integer.MAX_VALUE);

			distance[start] = 0;
			pQueue.offer(new Vertex(start, distance[start]));

			Vertex current = null;

			while (!pQueue.isEmpty()) {

				// 1단계 : 방문하지 않은 정점들 중에 출발지에서 자신까지 오는 비용이 최단인 정점을 고려할 경유지로 선택
				current = pQueue.poll();
				if (visited[current.no])
					continue; // PQ에 남아있던 totalDistance의 최소비용보다 더 큰 상태

				visited[current.no] = true;
				if (current.no == end)
					break;

				// 2단계 : 선택된 current 정점을 경유지로 해서 아직 방문하지 않은 다른 정점으로의 최단거리 비용 계산하여 유리하면 update
				for (int j = 1; j <= N; j++) {
					// min ==> distance[current]
					if (!visited[j] && map[current.no][j] != 0
							&& distance[j] > current.totalDistance + map[current.no][j]) {
						distance[j] = current.totalDistance + map[current.no][j];
						pQueue.offer(new Vertex(j, distance[j]));
					}
				}
			}
			if(distance[end]<=K) answer++;
		}

		return answer;
	}

	static class Vertex implements Comparable<Vertex> {
		int no, totalDistance; // totalDistance : 출발지에서 자신까지 오는 최단거리

		public Vertex(int no, int totalDistance) {
			super();
			this.no = no;
			this.totalDistance = totalDistance;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.totalDistance - o.totalDistance; // totalDistance가 작은 비용이 우선적으로 처리
		}
	}
}