프로그래머스 | 배달 (Java)

🔒문제

프로그래머스 Lv2. Summer/Winter Coding(~2018) 배달

🔑해결

마을의 개수 N, 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 배달 주문을 받을 수 있는 마을의 개수를 return하는 solution함수를 작성하는 문제이다.

다익스트라 알고리즘에 대해 공부하는 기회가 되는 문제였다.

1. 마을 번호 town과 이동 비용 cost를 매개변수로 갖는 Node 클래스를 생성
   1-1. Comparable 클래스를 implements하여 compareTo 메서드를 Override하여 작성. 비용으로 Node를 비교하게 함 -> 방문하지 않은 마을 중 최소 비용이 가장 작은 Node를 PriorityQueue를 사용해 찾기 위해 필요
2. 각 마을의 도로 정보를 list에 저장하는 map 생성
   2-1. 마을 번호를 index처럼 사용하기 위해 N+1개만큼 map에 Arraylist를 생성하여 add (ex. map.get(1)은 1번 마을과 연결된 Node(1번 마을과 연결된 마을 번호, 이동 비용) list이다.)
3. 주어진 도로 정보를 새 Node를 생성하여 마을 번호 index에 해당하는 ArrayList에 add
4. 방문 여부를 확인할 boolean배열 visited 생성
5. index번 마을까지 걸리는 최소 비용을 저장할 int 배열 min_cost 생성
6. 다익스트라 알고리즘
   6-1. 방문하지 않은 노드 중 비용이 가장 작은 노드를 target으로 하고, 해당 마을을 방문처리 한다.
   6-2. 인접 노드로의 최소 비용을 계산
   6-3. 6-1과 6-2를 반복
7. 최소 비용이 K 이하인 마을을 count하고 이를 return한다.

🔓코드

import java.util.ArrayList;
import java.util.PriorityQueue;
class Solution {
    class Node implements Comparable<Node>{

		int town; // 마을 번호
		int cost; // 이동 시간
		
		public Node (int town, int cost) {
			this.town = town;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.cost > o.cost ? 1 : -1;
		}

		@Override
		public String toString() {
			return "Node [town=" + town + ", cost=" + cost + "]";
		}
		
	}
	
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        
        ArrayList<ArrayList<Node>> map = new ArrayList<ArrayList<Node>>();
        for (int i = 0; i < N+1; i++) { 
        // 마을 번호가 1부터 시작하기 때문에 N+1개 만큼 add하여
        // 마을 번호를 index처럼 활용
			map.add(new ArrayList<Node>());
		}
        
        for (int i = 0; i < road.length; i++) {
            // 주어지는 도로 정보를 새 Node를 생성하여
            // 마을 번호 index에 해당하는 ArrayList에 add
            // 이어지는 두 마을 모두에 저장
			map.get(road[i][0]).add(new Node(road[i][1], road[i][2]));
			map.get(road[i][1]).add(new Node(road[i][0], road[i][2]));
		}
        
        // 방문 여부
        boolean[] visited = new boolean[N+1];
        // 최소 비용
        int[] min_cost = new int[N+1];
        for (int i = 0; i < min_cost.length; i++) {
			min_cost[i] = Integer.MAX_VALUE;
		}
        min_cost[1] = 0;
        
        // 다익스트라 알고리즘
        for (int i = 0; i < N; i++) {
			// 방문하지 않은 노드 중 가장 비용이 작은 노드
        	Node target = find_min_cost(visited, min_cost);
			visited[target.town] = true;
			
			// 인접 노드로의 최소 비용
			ArrayList<Node> around = map.get(target.town);
			for (int j = 0; j < around.size(); j++) {
				if (min_cost[around.get(j).town] > around.get(j).cost + target.cost) {
					min_cost[around.get(j).town] = around.get(j).cost + target.cost;
				}
			}
		}
        
        // 최소 비용이 K 이하인 마을 count
        for (int i = 1; i < min_cost.length; i++) {
			if (min_cost[i] <= K)
				answer++;
		}
        
        return answer;
    }
    private Node find_min_cost(boolean[] visited, int[] min_cost) {
    	PriorityQueue<Node> pq = new PriorityQueue<>();
    	for (int i = 1; i < min_cost.length; i++) {
			if (!visited[i]) { 
            	// 방문하지 않은 마을의 최소 비용을
                // PriorityQueue에 add
				pq.add(new Node(i, min_cost[i]));
			}
		}
    	return pq.peek(); // 최소 비용이 가장 작은 Node를 return
    }
}