이번에 풀어본 문제는
프로그래머스 배달 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Town {
    int n, time;
    public Town(int n, int time) {
        this.n = n;
        this.time = time;
    }
}

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        List<List<Town>> map = new ArrayList<>();

        for (int i = 0; i <= N; i++) map.add(new ArrayList<>());

        for (int [] r: road) {
            map.get(r[0]).add(new Town(r[1], r[2]));
            map.get(r[1]).add(new Town(r[0], r[2]));
        }

        int [] minTimes = new int[N + 1];
        Arrays.fill(minTimes, Integer.MAX_VALUE);
        minTimes[1] = 0;

        Queue<Town> q = new PriorityQueue<>(new Comparator<Town>() {
            @Override
            public int compare(Town o1, Town o2) {
                return o1.time - o2.time;
            }
        });

        q.add(new Town(1, 0));
        boolean [] isVisited = new boolean[N + 1];
        
        while (!q.isEmpty()) {
            Town cur = q.poll();

            if (!isVisited[cur.n]) {
                isVisited[cur.n] = true;
                
                for (Town next: map.get(cur.n)) {
                    if (!isVisited[next.n] && minTimes[next.n] > cur.time + next.time) {
                        minTimes[next.n] = cur.time + next.time;
                        q.add(new Town(next.n, minTimes[next.n]));
                    }
                }
            }
        }
        for (int time: minTimes) {
            if (time <= K) answer++;
        }
        return answer;
    }
}

📝 풀이

1번 마을에서 K시간 안에 갈 수 있는 인접한 마을의 수를 반환하는 문제입니다.
한 정점이 기준이 된다는 점에서 다익스트라가 떠올랐습니다.
1번 정점을 기준으로 최단경로를 구해주고, K이하에 속하는 값의 개수를 반환해주면 해결할 수 있습니다.