[프로그래머스] (Java) 배달 - 다익스트라 알고리즘

728x90

[프로그래머스] (Java) 배달 - 다익스트라 알고리즘

문제 설명

N개의 마을로 이뤄진 나라는 아래의 특징을 지닌다.

각 마을에는 1 ~ N까지 번호가 각각 하나씩 부여되어 있다.
각 마을은 양방향 도로로 연결되어 있다.
도로를 지날 때 소요되는 시간은 도로별로 다르다.

1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 할 때, N개 마을 중에서 K시간 이하로 배달이 가능한 마을의 개수를 구하려고 한다.

예를 들어, N = 5, K = 3인 경우 위와 같은 마을이 있다면,

1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지 3 이하의 시간에 배달할 수 있다. 그러나 3번 마을은 3시간이 초과되므로 3번 마을에서는 주문을 받지 않아, 최종적으로 주문을 받을 수 있는 마을의 개수는 4개가 된다.

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

제한 사항

마을의 개수 N은 1 이상 50 이하의 자연수
road 는 도로 정보를 담는 배열
road 의 길이는 1 이상 2000 이하
road 는 길이가 3인 배열을 담는 배열
- a, b (1 <= a, b <= N, a != b) 는 도로로 연결되어 있는 두 마을의 번호
- c (1 <= c <= 10000, c 자연수) 는 도로를 지날 때 소요되는 시간
- a, b 를 연결하는 도로는 여러 개가 있을 수도 있음
- 한 도로의 정보는 한 번만 주어짐
K 는 음식 배달이 가능한 시간
K 는 1 이상 500000 이하
임의의 두 마을은 항상 이동 가능한 경로가 존재

입출력 예

N	road	K	result
5	[[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]]	3	4
6	[[1, 2, 1], [1, 3, 2], [2, 3, 2], [3, 4, 3], [3, 5, 2], [3, 5, 3], [5, 6, 1]]	4	4

입출력 예 설명

[입출력 예 #1]

문제 예시와 같음

[입출력 예 #2]

1번 마을에서 4시간 이하가 걸리는 마을은 [1, 2, 3, 5] 4개이므로 4를 return

정답 코드

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        int[] distance = new int[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[1] = 0;

        List<int[]>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] r : road) {
            graph[r[0]].add(new int[]{r[1], r[2]});
            graph[r[1]].add(new int[]{r[0], r[2]});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{1, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int dist = current[1];

            if (dist > distance[node]) continue;

            for (int[] neighbor : graph[node]) {
                int nextNode = neighbor[0];
                int cost = neighbor[1];
                if (distance[nextNode] > distance[node] + cost) {
                    distance[nextNode] = distance[node] + cost;
                    pq.add(new int[]{nextNode, distance[nextNode]});
                }
            }
        }

        int answer = 0;
        for (int d : distance) {
            if (d <= K) answer++;
        }
        return answer;
    }
}

코드 풀이

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

1번 마을에서 N번 마을까지의 최단 거리를 담는 배열을 생성하여, 최대 거리(Integer.MAX_VALUE)로 초기화해준다.

(ex. distance[4] 는 1번 마을에서 4번 마을까지의 최단 거리)

그리고 1번 마을에서 1번 마을까지의 거리인 distance[1] 은 0으로 초기화해준다.

List<int[]>[] graph = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
    graph[i] = new ArrayList<>();
}
for (int[] r : road) {
    graph[r[0]].add(new int[]{r[1], r[2]});
    graph[r[1]].add(new int[]{r[0], r[2]});
}

마을의 구조를 담는 graph 를 생성한다.

i 번의 마을과 연결된 마을과의 정보를 담을 ArrayList를 생성해 주고,

(ex. graph[3] 은 3번 마을과 연결될 마을의 정보를 담을 List)

도로의 정보가 들어있는 road 를 순회하며 각각의 마을과 연결된 정보를 ArrayList에 추가한다.

(ex. r이 [1, 2, 4] 인 경우 1번 마을과 2번 마을을 잇는 거리가 4인 양방향 도로가 존재하는 것이니,

graph[1] 리스트에 [2, 4] 배열을 추가하고,

graph[2] 리스트에 [1, 4] 배열을 추가한다.)

graph 의 구조

0 ArrayList

1 ArrayList + add[연결된 마을, 거리]...

2 ArrayList

3 ArrayList

...

N ArrayList

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.add(new int[]{1, 0});

PriorithQueue 를 이용하여 거리가 짧은 순으로 큐를 항상 재배열하도록 한다.

처음 시작하는 부분인 1번 마을에서 1번 마을까지의 최단거리 0을 뜻하는 {1, 0}을 큐에 추가한다.

이때 재배열 하는 이유는, 연결된 마을 거리가 최단 거리로 계산된 것으로 사용해야 하기 때문이다.

(ex. 큐에 (3, 5), (2, 10), (2, 7) 로 1번 마을에서 2번 마을의 최단 거리가 10인 경우와 7인 경우가 들어있다고 하면,

10이 아닌 7로 계산해야지 2번 마을을 거쳐서 다른 마을로 가는 최단 거리를 알맞게 계산할 수 있다.

(3, 5), (2, 10)이 있는 큐에서 계산을 하던 중,

2번 마을까지의 최단 거리 7을 찾게 되어 (2, 7)을 큐에 add 했다고, 이미 큐에 있는 (2, 10)이 사라지지 않기 때문에 거리가 짧은 순으로 정렬하여 2번 마을까지의 최단거리를 (2, 10)이 아닌 (2, 7)로 사용해야 한다.)

while (!pq.isEmpty()) {
    int[] current = pq.poll();
    int node = current[0];
    int dist = current[1];

    if (dist > distance[node]) continue;

    for (int[] neighbor : graph[node]) {
        int nextNode = neighbor[0];
        int cost = neighbor[1];
        if (distance[nextNode] > distance[node] + cost) {
            distance[nextNode] = distance[node] + cost;
            pq.add(new int[]{nextNode, distance[nextNode]});
        }
    }
}

pq 에서 가장 최단거리인 노드를 하나씩 빼서 계산하고, 해당 노드와 연결된 next노드들을 for 문을 통해 순회한다.

이때, distance 에 기록되어 있는 next노드의 최단 거리보다 해당 노드의 최단거리 + next노드와 연결된 거리가 더 작은 경우

distance 에 next노드의 최단거리를 해당 노드의 최단거리 + next노드와 연결된 거리로 업데이트하고,

[next노드, 새로운 최단 거리]를 담은 배열을 큐에 추가한다.

(distance 에 기록되어 있는 next노드의 최단 거리보다 해당 노드의 최단거리 + next노드와 연결된 거리가 더 작은 경우에 [next노드, 새로운 최단 거리]를 큐에 추가하는 과정에서, 큐에 기존에 있던 [next노드, 최단 거리] 것을 삭제하지 않고 큐에 추가해 주는 것이기 때문에 최단 거리로 정렬해서 사용해야 한다.)

int answer = 0;
for (int d : distance) {
    if (d <= K) answer++;
}
return answer;

각 마을과의 최단 거리가 기록된 distance 를 순회하며 배달 가능한 시간이 K 이하인 마을들의 개수를 카운트 해준 뒤 리턴한다.

풀이 상세

새로운 예시로 설명해 보겠다.

N : 4

road : [[1, 2, 10], [1, 3, 5], [3, 2, 2], [3, 4, 9], [2, 4, 1]]

K : 7

그래프

0 :

1 : (2, 10) (3, 5)

2 : (1, 10) (3, 2) (4, 1)

3 : (1, 5) (2, 2) (4, 9)

4 : (3, 9) (2, 1)

초기 상태

distance : [∞, 0, ∞, ∞, ∞]

큐 : [(1, 0)]

큐에서 poll → (1, 0)

현재 node : 1

현재 거리 : 0

그래프에서 1번 마을과 연결된 마을을 순회

i (2, 10)

next node : 2

next 거리 : 10

distance[2] > 현재 거리 + next 거리 → true

distance[2] = 0 + 10 → distance : [∞, 0, 10, ∞, ∞]

큐에 (2, 10) 추가 → 큐 : [(2, 10)]

ii (3, 5)

next node : 3

next 거리 : 5

distance[3] > 현재 거리 + next 거리 → true

distance[3] = 0 + 5 → distance : [∞, 0, 10, 5, ∞]

큐에 (3, 5) 추가 → 큐 : [(2, 10) (3, 5)] → 정렬 → 큐 : [(3, 5) (2, 10)]

큐에서 poll → (3, 5)

현재 node : 3

현재 거리 : 5

그래프에서 3번 마을과 연결된 마을을 순회

i (1, 5)

next node : 1

next 거리 : 5

distance[1] > 현재 거리 + next 거리 → false

continue;

ii (2, 2)

next node : 2

next 거리 : 2

distance[2] > 현재 거리 + next 거리 → true

distance[2] = 5 + 2 → distance : [∞, 0, 7, 5, ∞]

큐에 (2, 7) 추가 → 큐 : [(2, 10) (2, 7)] → 정렬 → 큐 : [(2, 7) (2, 10)]

iii (4, 9)

next node : 4

next 거리 : 9

distance[4] > 현재 거리 + next 거리 → true

distance[4] = 5 + 9 → distance : [∞, 0, 7, 5, 14]

큐에 (4, 14) 추가 → 큐 : [(2, 7) (2, 10) (4, 14)]

큐에서 poll → (2, 7)

현재 node : 2

현재 거리 : 7

그래프에서 2번 마을과 연결된 마을을 순회

i (1, 10)

next node : 1

next 거리 : 10

distance[1] > 현재 거리 + next 거리 → false

continue;

ii (3, 2)

next node : 3

next 거리 : 2

distance[3] > 현재 거리 + next 거리 → false

continue;

iii (4, 1)

next node : 4

next 거리 : 1

distance[4] > 현재 거리 + next 거리 → true

distance[4] = 7 + 1 → distance : [∞, 0, 7, 5, 8]

큐에 (4, 8) 추가 → 큐 : [(2, 10) (4, 14) (4, 8)] → 정렬 → 큐 : [(4, 8) (2, 10) (4, 14)]

큐에서 poll → (4, 8)

현재 node : 4

현재 거리 : 8

그래프에서 4번 마을과 연결된 마을을 순회

i (3, 9)

next node : 3

next 거리 : 9

distance[1] > 현재 거리 + next 거리 → false

continue;

ii (2, 1)

next node : 2

next 거리 : 1

distance[3] > 현재 거리 + next 거리 → false

continue;

큐에서 poll → (2, 10)

현재 node : 2

현재 거리 : 10

그래프에서 2번 마을과 연결된 마을을 순회

i (1, 10)

next node : 3

next 거리 : 9

distance[1] > 현재 거리 + next 거리 → false

continue;

ii (3, 2)

next node : 3

next 거리 : 2

distance[3] > 현재 거리 + next 거리 → false

continue;

ii (4, 1)

next node : 4

next 거리 : 1

distance[3] > 현재 거리 + next 거리 → false

continue;

큐에서 poll → (4, 14)

현재 node : 4

현재 거리 : 14

그래프에서 2번 마을과 연결된 마을을 순회

i (3, 9)

next node : 3

next 거리 : 9

distance[1] > 현재 거리 + next 거리 → false

continue;

ii (2, 1)

next node : 2

next 거리 : 1

distance[3] > 현재 거리 + next 거리 → false

continue;

큐가 비었으므로 종료!

distance : [∞, 0, 7, 5, 8]

728x90

'💠문제 풀이 > 코딩 테스트 문제 풀이' 카테고리의 다른 글

[프로그래머스] (JavaScript) 단어 변환 - BFS (0)	2024.06.07
[프로그래머스] (JavaScript) 네트워크 - DFS (0)	2024.06.05
[프로그래머스] (JavaScript) 타겟 넘버 - DFS (1)	2024.06.03
[프로그래머스] (JavaScript) 피로도 - DFS (1)	2024.06.01