[프로그래머스] 배달

프로그래머스

 

💬 문제 설명

N개의 마을이 있고 각 마을은 도로로 연결되어 있다. 마을 간 이동 시간은 제각각 다르므로 1번 마을에서 각 마을까지의 최소 이동 시간을 구하려고 한다. 그 최소 이동 시간이 K 이하인 마을의 개수를 반환하라.

 

📌 주의 사항

• A 마을과 B 마을을 잇는 도로가 여러 개 존재할 수 있으므로 그럴 경우 이동 시간이 적은 도로의 정보를 저장한다.

 

👌 문제 풀이

1. 이동 시간을 저장하는 인접 행렬 정의
   • INF 값으로 초기화
   • `Math.min()`으로 이동 시간이 제일 작은 도로의 정보를 저장
2. 다익스트라 알고리즘으로 1번 마을에서 시작하여 각 마을로 이동하는 최소 이동 거리 계산
   • 최소 이동 시간 배열 정의
   • 최소힙 활용

 

💻 코드

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

class Solution {
    
    int[][] map;
    
    public int solution(int N, int[][] road, int K) {
    	// 1. 이동 시간을 저장하는 인접 행렬 정의
        // 1번부터 시작
        map = new int[N + 1][N + 1];
        
        for (int i = 0; i <= N; i++) {
            // 이동 시간이 제일 작은 도로의 정보를 저장하기 위해 큰 값으로 초기화
            Arrays.fill(map[i], Integer.MAX_VALUE);
        }
       	
        // 2. 입력 값 저장
        for (int[] e : road) {
            // 이미 저장된 값인 경우 최소값으로 갱신
            map[e[0]][e[1]] = Math.min(map[e[0]][e[1]], e[2]);
            map[e[1]][e[0]] = Math.min(map[e[1]][e[0]], e[2]);
        }
        
        // 3. 다익스트라로 모든 마을까지의 최소 이동 거리 계산
        return dijkstra(N, K);
    }
    
    int dijkstra(int n, int k) {
    	// 최소 이동 시간을 저장하는 배열 정의 및 초기화
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        // 최소 이동 시간부터 확인하기 위해 minHeap 사용
        Queue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(1, 0)); // 1번 마을에서 시작
        dist[1] = 0; // 1번 마을의 최소 이동 시간을 0으로 초기화
        
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            
            for (int next = 2; next <= n; next++) {
                if (map[cur.v][next] != Integer.MAX_VALUE) { // 연결된 마을일 경우
                    int nextW = map[cur.v][next];
                    // 이동할 마을의 최소 이동 시간 > 현재 마을을 거쳐서 가는 이동 시간이면
                    // 이동할 마을의 최소 이동 시간 갱신
                    if (dist[next] > dist[cur.v] + nextW) {
                        dist[next] = dist[cur.v] + nextW;
                        queue.offer(new Node(next, dist[next]));
                    }
                }
            }
        }
        
        // 이동 시간이 K보다 작은 마을의 개수 세기
        int cnt = 0;
        for (int d : dist) {
            if (d <= k) {
                cnt++;
            }
        }
        return cnt;
    }
    
}

class Node implements Comparable<Node> {
    
    // 정점, 정점으로 이동하는 시간
    int v, w;
    
    Node(int v, int w) {
        this.v = v;
        this.w = w;
    }
    
    // 이동 시간을 오름차순으로 정렬
    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.w, o.w);
    }
    
}

 

🎓 배운 것

1. 테스트케이스를 잘 확인하자!