문제
N개의 마을에 1부터 N까지 번호가 부여되어 있음
마을들은 양방향 도로가 존재
1번 마을에서 각 마을에 음식 배달
K 시간 이하로 걸리는 마을만 배달 가능
배달 할 수 있는 마을의 개수를 구하라
마을 개수 N은 1이상 50이하
road의 길이(도로 정보의 개수)는 1이상 2,000이하
road의 각 원소는 (a, b, c)로 이루어져 있음
a, b는 마을 번호, c는 도로를 지나는데 걸리는 시간
도로 정보는 중복되지 않음
K는 배달 가능 시간이며, 1이상 500,000 이하
입출력 예시
| 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 |
접근
그래프 최단 경로 문제이다.
다익스트라 알고리즘을 이용하여 한 마을(1번)에서부터 다른 마을로의 최단경로를 모두 구한다.
그 후 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
import heapq
def solution(N, road, K):
heap = []
v = [[] for i in range(N+1)]
d = [987654321 for i in range(N+1)]
for x, y, n in road:
v[x].append([n, y])
v[y].append([n, x])
d[1] = 0
heapq.heappush(heap, [d[1], 1])
while len(heap) > 0:
now = heapq.heappop(heap)
if(d[now[1]] != now[0]):
continue
for nxt in v[now[1]]:
if d[nxt[1]] > now[0] + nxt[0]:
d[nxt[1]] = now[0] + nxt[0]
heapq.heappush(heap, [d[nxt[1]], nxt[1]])
cnt = 0
for i in range(1, len(d)):
if d[i] <= K:
cnt += 1
return cnt