문제 설명
문제 설명 생략
🙋♂️나의 풀이
🤔문제 접근
다익스트라 알고리즘을 적용해서 풀었다. 그래프 문제는 처음이라 자료를 찾아가며 풀었다.
1번 마을에서 K 시간 안에 배달이 가능한 마을이 몇 개 있는지 구해야 한다.
주어진 시간 안에 이동하기 위해서는 최단 시간으로 이동하는 것이 좋기 때문에 다익스트라 알고리즘을 사용한다.
최단 경로를 구하는 알고리즘은 대표적으로 3가지가 있다.
- 다익스트라 알고리즘
- 벨만포드 알고리즘
- 플로이드 워샬 알고리즘
벨만포드 알고리즘은 경로의 길이가 음수일 경우 사용하면 유리하지만, 이 문제에서는 경로의 길이가 음수인 경우는 없으므로 사용하지 않는다.
다음으로 플로이드 워샬 알고리즘은 하나의 노드에서 다른 노드까지 최단경로와 모든 노드 간에 최단경로를 구할 수 있다. 하지만, 이 문제에서는 모든 노드 사이의 최단 경로를 구할 필요는 없기 때문에 다익스트라 알고리즘을 사용해서 구현하는 것이 적절하다.
다익스트라 알고리즘으로 1번 마을에서 각각의 마을의 최단 시간을 구했다면, 이 값 중에서 K 시간 안에 이동할 수 있는 마을의 개수를 세면 된다.
✍️작성 코드
순차 탐색 방식으로 구현했다.
우선, 2차원 배열 형태의 그래프를 만들기 위해 createGraph 함수를 사용했다.
1
2
3
4
5
6
7
8
9
10
11
const createGraph = (N, road) => {
const graph = Array.from(Array(N), () => Array(N).fill(Infinity));
road.forEach((info) => {
const [n1, n2, d] = info;
if (graph[n1 - 1][n2 - 1] > d) {
graph[n1 - 1][n2 - 1] = d;
graph[n2 - 1][n1 - 1] = d;
}
});
return graph;
};
두 마을을 연결하는 경로는 2가지 이상일 수 있기 때문에 다음과 같이 이전에 저장된 값과 비교하는 조건을 추가했다.
1
if (graph[n1 - 1][n2 - 1] > d)
그러면 다음과 같이 직접 연결된 마을 간의 거리 정보를 저장한 2차원 배열이 생성된다.
1
2
3
4
5
6
7
[
[Infinity, 1, Infinity, 2, Infinity],
[1, Infinity, 3, Infinity, 2],
[Infinity, 3, Infinity, Infinity, 1],
[2, Infinity, Infinity, Infinity, 2],
[Infinity, 2, 1, 2, Infinity],
];
1번 마을에서 각 마을까지 방문 여부를 표시하기 위한 visited 배열은 다음과 같이 생성했다.
1
const visited = Array(N).fill(false);
1번 마을에서 각 마을마다 직접 연결된 경로를 저장하기 위한 distance 배열은 다음과 같이 생성했다.
1
2
3
const distance = visited.map((_, i) => {
return graph[0][i];
});
각 마을 간 최단거리를 계산하는 다익스트라 알고리즘 함수는 다음과 같이 작성했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const dijkstra = (graph, visited, distance) => {
distance[0] = 0; // 자기 자신은 거리가 0 으로 설정
visited[0] = true; // 자기 자신은 이미 방문한 것으로 설정
for (let i = 0; i < distance.length; i++) {
const nodeIdx = findSmallestNode(visited, distance); // 인접 노드 중 방문하지 않았고, 거리가 짧은 마을 선택
visited[nodeIdx] = true; // 이동한 마을은 방문 처리
for (let j = 0; j < distance.length; j++) {
if (visited[j]) continue ;
// (이전 경로까지의 합 + 방문한 마을과 다음 방문할 마을 간의 거리)가 최소 경로인 경우 갱신
if (distance[j] > distance[nodeIdx] + graph[nodeIdx][j]
distance[j] = distance[nodeIdx] + graph[nodeIdx][j];
}
}
}
완성한 코드는 다음과 같다.
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
40
41
42
43
44
45
46
47
48
49
50
function solution(N, road, K) {
let answer = 0;
const graph = createGraph(N, road);
const visited = Array(N).fill(false);
const distance = visited.map((_, i) => {
return graph[0][i];
});
dijkstra(graph, visited, distance);
return distance.filter((d) => d <= K).length;
}
const createGraph = (N, road) => {
const graph = Array.from(Array(N), () => Array(N).fill(Infinity));
road.forEach((info) => {
const [n1, n2, d] = info;
if (graph[n1 - 1][n2 - 1] > d) {
graph[n1 - 1][n2 - 1] = d;
graph[n2 - 1][n1 - 1] = d;
}
});
return graph;
};
const findSmallestNode = (visited, distance) => {
let minDist = Infinity;
let minIdx = 0;
for (let i = 0; i < distance.length; i++) {
if (visited[i]) continue;
if (distance[i] < minDist) {
minDist = distance[i];
minIdx = i;
}
}
return minIdx;
};
const dijkstra = (graph, visited, distance) => {
distance[0] = 0;
visited[0] = true;
for (let i = 0; i < distance.length; i++) {
const nodeIdx = findSmallestNode(visited, distance);
visited[nodeIdx] = true;
for (let j = 0; j < distance.length; j++) {
if (visited[j]) continue;
if (distance[j] > distance[nodeIdx] + graph[nodeIdx][j])
distance[j] = distance[nodeIdx] + graph[nodeIdx][j];
}
}
};
채점 결과는 다음과 같다.
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
테스트 1 〉 통과 (0.24ms, 29.9MB)
테스트 2 〉 통과 (0.24ms, 29.9MB)
테스트 3 〉 통과 (0.24ms, 30MB)
테스트 4 〉 통과 (0.25ms, 30MB)
테스트 5 〉 통과 (0.25ms, 29.9MB)
테스트 6 〉 통과 (0.21ms, 29.8MB)
테스트 7 〉 통과 (0.27ms, 29.9MB)
테스트 8 〉 통과 (0.26ms, 29.9MB)
테스트 9 〉 통과 (0.23ms, 29.8MB)
테스트 10 〉 통과 (0.24ms, 29.8MB)
테스트 11 〉 통과 (0.25ms, 29.9MB)
테스트 12 〉 통과 (0.42ms, 29.9MB)
테스트 13 〉 통과 (0.36ms, 29.9MB)
테스트 14 〉 통과 (0.67ms, 30.2MB)
테스트 15 〉 통과 (0.89ms, 30MB)
테스트 16 〉 통과 (0.28ms, 30.1MB)
테스트 17 〉 통과 (0.34ms, 29.8MB)
테스트 18 〉 통과 (0.57ms, 29.9MB)
테스트 19 〉 통과 (0.86ms, 30MB)
테스트 20 〉 통과 (0.56ms, 30MB)
테스트 21 〉 통과 (0.92ms, 30.1MB)
테스트 22 〉 통과 (0.61ms, 29.9MB)
테스트 23 〉 통과 (0.94ms, 30MB)
테스트 24 〉 통과 (0.83ms, 30MB)
테스트 25 〉 통과 (21.39ms, 32.5MB)
테스트 26 〉 통과 (18.91ms, 32.6MB)
테스트 27 〉 통과 (20.04ms, 32.6MB)
테스트 28 〉 통과 (24.76ms, 32.7MB)
테스트 29 〉 통과 (2.04ms, 32MB)
테스트 30 〉 통과 (1.97ms, 32.9MB)
테스트 31 〉 통과 (0.53ms, 30MB)
테스트 32 〉 통과 (0.62ms, 30MB)
⚙️ 리팩토링
순차 탐색 방식은 ‘방문하지 않은 노드 중 거리값이 가장 작은 노드’를 다음 탐색 노드로 선택한다. 그 노드를 찾는 방식은 거리 테이블의 앞에서부터 찾아내야 하기 때문에 시간 복잡도는 $O(N^2)$ 이 된다.
시간 복잡도를 줄이기 위해 $O(log\ n)$ 을 보장하는 우선순위 큐를 사용한다. 다만, 우선순위 큐 자체를 구현하기 보다 우선순위 큐 개념을 이용했다.
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
function solution(N, road, K) {
const dist = Array(N + 1).fill(Infinity);
const graph = Array.from(Array(N + 1), () => []);
road.forEach((info) => {
const [n1, n2, d] = info;
graph[n1].push({ to: n2, dist: d });
graph[n2].push({ to: n1, dist: d });
});
const queue = [{ to: 1, dist: 0 }];
dist[1] = 0;
while (queue.length) {
const { to } = queue.pop();
graph[to].forEach((next) => {
const acc = dist[to] + next.dist;
if (dist[next.to] > acc) {
dist[next.to] = acc;
queue.push(next);
}
});
}
return dist.filter((item) => item <= K).length;
}
1번 마을과 직접 연결된 마을 간의 거리를 저장하는 dist 에서 N 이 아닌 N + 1 만큼 길이로 생성한 이유는 0 번 인덱스는 비어있는 인덱스로 사용하기 위함이다. road 에 저장된 마을의 번호가 0 부터 시작하지 않기 때문이다.
마찬가지로 각 마을마다 연결된 정보를 저장하는 graph 에도 N + 1 길이만큼 2차원 배열을 생성했다. 그리고 각 배열에는 객체 형태로 목적지 to 와 거리 dist 를 저장했다.
1
2
3
4
5
road.forEach((info) => {
const [n1, n2, d] = info;
graph[n1].push({ to: n2, dist: d });
graph[n2].push({ to: n1, dist: d });
});
graph 에는 다음과 같이 저장된다.
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
[
[], // 0번 인덱스는 사용X
[
{ to: 2, dist: 1 },
{ to: 4, dist: 2 },
],
[
{ to: 1, dist: 1 },
{ to: 3, dist: 3 },
{ to: 5, dist: 2 },
],
[
{ to: 2, dist: 3 },
{ to: 5, dist: 1 },
],
[
{ to: 1, dist: 2 },
{ to: 5, dist: 2 },
],
[
{ to: 2, dist: 2 },
{ to: 3, dist: 1 },
{ to: 4, dist: 2 },
],
];
그 다음 큐에 1번 마을에 대한 정보를 넣고, 1번 마을까지의 거리를 0 으로 설정했다.
1
2
const queue = [{ to: 1, dist: 0 }];
dist[1] = 0;
큐에서 하나씩 꺼내서 다음 경로까지 최단 경로를 dist 에 갱신한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (queue.length) {
// 방문 대상
const { to } = queue.pop();
// 방문 대상과 연결된 모든 마을을 순회
graph[to].forEach((next) => {
// 1번 마을까지 누적된 거리 + 연결된 대상까지 거리
const acc = dist[to] + next.dist;
if (dist[next.to] > acc) {
dist[next.to] = acc;
queue.push(next);
}
});
}
채점 결과는 다음과 같다. 테스트 25 ~ 28 은 실행 시간이 이전보다 확연하게 감소했다.
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
테스트 1 〉 통과 (0.53ms, 30MB)
테스트 2 〉 통과 (0.38ms, 30.1MB)
테스트 3 〉 통과 (0.51ms, 29.8MB)
테스트 4 〉 통과 (0.42ms, 30.1MB)
테스트 5 〉 통과 (0.47ms, 30MB)
테스트 6 〉 통과 (0.20ms, 30.1MB)
테스트 7 〉 통과 (0.37ms, 29.9MB)
테스트 8 〉 통과 (0.35ms, 29.8MB)
테스트 9 〉 통과 (0.43ms, 29.9MB)
테스트 10 〉 통과 (0.40ms, 29.8MB)
테스트 11 〉 통과 (0.50ms, 29.9MB)
테스트 12 〉 통과 (0.41ms, 29.9MB)
테스트 13 〉 통과 (0.42ms, 30MB)
테스트 14 〉 통과 (2.38ms, 32MB)
테스트 15 〉 통과 (3.94ms, 32.4MB)
테스트 16 〉 통과 (0.37ms, 29.9MB)
테스트 17 〉 통과 (0.37ms, 30MB)
테스트 18 〉 통과 (1.07ms, 30MB)
테스트 19 〉 통과 (3.16ms, 32.5MB)
테스트 20 〉 통과 (0.89ms, 30MB)
테스트 21 〉 통과 (4.94ms, 33.2MB)
테스트 22 〉 통과 (1.90ms, 32MB)
테스트 23 〉 통과 (4.62ms, 32.4MB)
테스트 24 〉 통과 (4.48ms, 32.2MB)
테스트 25 〉 통과 (4.32ms, 33.2MB)
테스트 26 〉 통과 (5.57ms, 33.4MB)
테스트 27 〉 통과 (4.47ms, 33.4MB)
테스트 28 〉 통과 (4.35ms, 33.5MB)
테스트 29 〉 통과 (4.48ms, 33.5MB)
테스트 30 〉 통과 (2.60ms, 32.7MB)
테스트 31 〉 통과 (0.40ms, 30MB)
테스트 32 〉 통과 (0.63ms, 29.9MB)
참고자료
- [ 프로그래머스 배달 (Lv2) ] (C++) [티스토리]
- [ 다익스트라 알고리즘 ] 개념과 구현방법 (C++) [티스토리]
- [알고리즘] 다익스트라(Dijkstra) 알고리즘 [velog]
- [프로그래머스] 배달 - JavaScript [velog]