[Algorithm] 배달
쉰 세 번째 포스팅
안녕하세요! 쉰 세 번째 포스팅으로 찾아뵙게 되어 반갑습니다!♥
오늘의 포스팅 내용은 프로그래머스 - 배달에 관한 내용입니다.
자세한 내용을 알아보러 갑시다❗️
[Boongranii] Here We Go 🔥
1️⃣ 문제
💨 문제 설명
N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.
위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.
💨 제한 사항
- 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
- road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
- road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
- road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
- a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
- 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
- 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
- K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
- 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
- 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.
💨 입출력 예
| 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 합니다.
2️⃣ 문제 풀이
🔥 나의 문제 풀이
- graph를 초기화함. (graph는 마을과 마을 사이의 길에 대한 정보를 담고 있음)
- distance는 각 마을까지의 최단 거리를 담고 있음.
- queue는 bfs를 위한 queue임.
- 각 마을에서 길에 대한 cost 표현
- graph를 돌면서 각 마을까지의 최단 거리를 구함.
- 최단 거리가 K보다 작거나 같으면 추가함.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function solution(N, road, K) {
let answer = 0;
const graph = Array.from({ length: N + 1 }, () => Array()); // graph 초기화
const distance = Array.from({ length: N + 1 }, () => Infinity); // 각 마을까지의 최단 거리 distance 초기화
const queue = []; // BFS를 위한 queue 초기화
// 각 마을에서 길에 대한 cost 표현
road.forEach((r) => {
let [a, b, c] = r;
graph[b].push({ end: a, cost: c }); // 양방향 그래프이므로 양쪽으로 추가
graph[a].push({ end: b, cost: c });
});
queue.push(1); // 1번 마을부터 시작
distance[1] = 0; // 출발 지점까지의 거리는 0
// BFS 탐색 시작
while (queue.length) {
const currentVillage = queue.shift();
// 현재 마을과 연결된 마을들을 탐색
for (let i = 0; i < graph[currentVillage].length; i++) {
const nextVillage = graph[currentVillage][i].end;
const nextVillageCost = graph[currentVillage][i].cost;
// 최단 거리 갱신
if (distance[nextVillage] > distance[currentVillage] + nextVillageCost) {
distance[nextVillage] = distance[currentVillage] + nextVillageCost;
queue.push(nextVillage);
}
}
}
// 출발 지점으로부터 각 마을까지의 최단 거리 확인
for (let i = 1; i <= N; i++) {
answer += distance[i] > K ? 0 : 1; // 주어진 한계값 K 이하인 마을의 수 측정
}
return answer;
}
일단, 문제를 읽고 나서 다익스트라 알고리즘이 생각났다. 정확히 생각이 안나서 이곳을 참고했다. [다익스트라 알고리즘-wiki]
gif로만 후딱 이해가 가능했다. 만든 사람 대단..
이해는 잘 되었지만 이것을 도대체 어떻게 구현할 지가 정말 막막했다. 질문하기를 참조하며 어떻게 풀 지 써보았다.
일단 주어진 그래프를 배열 안에 넣어보고자 graph를 선언한다. distance는 각각의 마을까지의 최단 거리를 저장하는 배열이다. queue는 BFS를 위한 큐를 나타낸다.
일단 그림처럼 그래프 꼴로 해결할 수는 없으니, graph 배열에 각 마을에서 지나가는 길에 대한 cost와 end 비용과 목적지를 설정해 주었다.
이후에 시작 마을의 번호인 1번을 큐에 넣고, 출발 지점까지의 거리인 0을 distance를 통해 넣어주었다.
그리고 나서 BFS 탐색을 시작한다. 해당 노드와 인접한 노드를 먼저 방문하는 방식이므로 BFS라고 할 수 있다.
큐에서 현재방문 마을을 빼면서 해당 노드와 인접한 노드를 방문한다. for루프는 현재 마을과 연결된 모든 다음 마을을 탐색하는 것이다.
distance[nextVillage] > distance[currentVillage] + nextVillageCost 이 조건을 통해서 최단 거리를 갱신할 수 있다.
최단 거리가 업데이트 되었다면 해당 마을을 큐에 추가할 수 있으며 이렇게 해서 큐에서 이전에 처리하지 않은 마을에 대해 계속해서 탐색을 진행할 수 있다. 이 과정을 큐가 더 이상 비어있지 않을 때까지 반복하면 된다.
🔥 참고사항
1
2
const graph = Array.from({ length: N + 1 }, () => Array());
const graph = new Array(N + 1).fill([]);
위 둘의 차이점❓
1번은 Array.from() 메서드를 사용하여 새로운 배열을 만들고, 배열의 각 요소마다 빈 배열을 생성한다. 각 요소는 새로운 배열 객체를 참조하게 된다. 이 방법은 모든 요소가 서로 다른 배열 객체를 참조하기 때문에 하위 배열의 변경이 다른 요소에 영향을 주지 않는다.
2번은 이 방식은 먼저 길이가 N+1인 새로운 배열을 생성하고, 이 배열의 모든 요소를 빈 배열로 채운다. 하지만 fill() 메서드는 주어진 값(여기서는 빈 배열)의 참조를 사용하여 배열을 채우기 때문에, 모든 요소가 동일한 빈 배열 객체를 참조하게 된다. 이는 하위 배열의 변경이 모든 요소에 영향을 줄 수 있다.
따라서
두 가지 방식의 차이점은 요소가 각각 다른 배열 객체를 참조하느냐, 아니면 모든 요소가 동일한 배열 객체를 참조하느냐에 있다.
대부분의 경우 요소가 각각 다른 배열 객체를 참조하는 1번 방식을 사용하는 것이 안전하며 예기치 않은 부작용을 방지할 수 있다.
3️⃣ 느낀점
다익스트라 알고리즘은 처음 접하는 알고리즘이라 많이 당황했다.
어렵기도 했고 BFS를 통해 탐색을 해야 했다. 물론 모두 나의 힘으로 푼 건 아니더라도 코드에 적응할 수 있었던 좋은 문제였다고 생각한다.
앞으로도 이러한 문제가 나오면 당황하지 않고 풀 수 있기를 바래본다.
해결책을 향해 고어헤드 합시다. 화이텡구리털❗️💕
댓글남기기