[프로그래머스] 배달(Java, 자바)

문제

배달

📌 아이디어

해당 문제는 노드 간의 최단 거리를 구하는 문제이기 때문에 다익스트라 알고리즘을 적용해 문제를 해결했습니다.

1. 양방향 연결로 인접 리스트를 생성했습니다.
2. 최단 거리를 구해야되기 때문에 visited 배열을 최대값으로 초기화했습니다.
3. 큐 자료구조를 활용해 탐색을 진행하였고, 다음 노드의 visited가 더 크다면 최단 거리로 재할당했습니다.
4. 탐색이 끝난 후에 K보단 작은 값들을 카운트해 정답을 도출했습니다.

📌 코드

import java.util.*;

class 배달 {
    static int cnt = 1;
    static int[] visited;
    static class Node {
        // 출발, 도착, 시간
        int x, y, v;

        Node(int x, int y, int v) {
            this.x = x;
            this.y = y;
            this.v = v;
        }
    }
    public int solution(int N, int[][] road, int K) {
        ArrayList<ArrayList<Node>> lst = new ArrayList<>();
        for (int i=0; i<=N; i++) {
            lst.add(new ArrayList<>());
        }
        // 양방향 연결
        for (int[] r : road) {
            lst.get(r[0]).add(new Node(r[0], r[1], r[2]));
            lst.get(r[1]).add(new Node(r[1], r[0], r[2]));
        }
        visited = new int[N+1];
        for (int i = 2; i<visited.length; i++) {
            visited[i] = Integer.MAX_VALUE;
        }
        bfs(lst.get(1), lst, K);
        return cnt;
    }
    public void bfs(ArrayList<Node> node, ArrayList<ArrayList<Node>> lst, int K) {
        Queue<Node> que = new LinkedList<>();
        que.addAll(node);

        while (!que.isEmpty()) {
            Node n = que.poll();
			// 최단 거리 할당
            if(visited[n.y] >= visited[n.x] + n.v) {
                visited[n.y] = visited[n.x] + n.v;
                que.addAll(lst.get(n.y));
            }
        }

        for (int i=2; i<visited.length; i++) {
            if (visited[i] <= K) cnt++;
        }
    }
}

✏️ TIP : 큐에 여러 인자가 들어갈 경우 클래스를 생성하고 생성자를 활용해 값을 할당해주자!!

피드백 및 개선점은 댓글을 통해 알려주세요😊