URL : https://programmers.co.kr/learn/courses/30/lessons/12978
문제
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 하면 됩니다
문제풀이
- 다익스트라를 사용해 풀어야함
- visted라는 방문 노드를 생성 -> 처음 시작인 0번 마을(시작 루트)는 주어지지 않으므로 N + 1을 해줘야함
- road는 [마을1, 마을2, 거리]순으로 마을1에서 마을2로 가는 방식으로 주어져 있음
- 이를 [거리, 마을]로 바꿔야주어야함
- 시작 마을은 visited의 index임
- 전체 마을에 대한 거리 초기 설정 distance 생성, 거리는 모두 inf로 기본값 셋팅
- heap 생성, 처음 0번 마을에서 1번 마을로 가는 거리는 0임
- 이후 heap에 heappush와 heappop을 이용하여 마을의 거리와 노드를 출력
- 만일 마을의 거리가 기존 방문한 거리보다 짧으면 갱신, 아니면 넘어감
- 모두 완료후 주어진 k보다 작거나 같은 distance를 출력
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
import heapq
def solution(N, road, k):
# 각 마을의 연결 노드 생성, 처음 시작인 0번 마을은 없기 떄문에 +1을 해줌
visited = [[] for i in range(N + 1)]
# [[], [], [], [], [], []]
# road = [마을1, 마을2, 거리]로 되어있는것을 -> [거리, 마을]로 변경, 시작 마을은 visited의 index임
for r in road:
# 마을1 정보에 대한 거리를 (거리, 도착 마을)로 설정
visited[r[0]].append([r[2], r[1]])
# 마을2 정보에 대한 거리를 (거리, 도착 마을)로 설정
visited[r[1]].append([r[2], r[0]])
# [[], 0번 마을
# [[1, 2], [2, 4]], 1번 마을, 2번 마을로가는데 1의 거리, 4번 마을로 가는데 2의 거리
# [[1, 1], [3, 3], [2, 5]],
# [[3, 2], [1, 5]],
# [[2, 1], [2, 5]],
# [[2, 2], [1, 3], [2, 4]]]
# 전체 마을에 대한 거리 초기 설정 (모두 inf), 처음 시작인 0번 마을은 없기 떄문에 +1을 해줌
distance = [float('inf')] * (N + 1)
# heap 시작 설정
heap = []
# 처음 0번 마을에서 1번 마을로 가는 거리는 0임
heapq.heappush(heap, [0, 1])
# 1번 마을의 거리 설정 -> 0
distance[1] = 0
# heap이 비기 전까지
while heap:
# heap에서 맨 앞에(루트)
cost, node = heapq.heappop(heap)
# 방문지의 cost, node
for c, n in visited[node]:
# 방문지의 cost와 현재 cost를 더 한게 거리의 합보다 낮으면 갱신
if cost + c < distance[n]:
distance[n] = cost + c
heapq.heappush(heap, [cost + c, n])
# 주어진 k보다 distance가 작은것을 출력
return len([dis for dis in distance if k >= dis])
1
2
3
4
5
N = 5
road = [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]
k = 3
solution(N, road, k)
1
4
1
2
3
4
5
N = 6
road = [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,3],[3,5,2],[5,6,1]]
k = 4
solution(N, road, k)
1
4
1
2
3
4
5
6
7
8
9
10
11
# heapq heappush
heap = [] # 사실 그냥 리스트
heapq.heappush(heap, 14)
print(heap)
heapq.heappush(heap, 10)
print(heap)
heapq.heappush(heap, 5)
print(heap)
1
2
3
[14]
[10, 14]
[5, 14, 10]
1
2
3
4
5
6
7
# heapq pop
heapq.heappop(heap)
print(heap)
heapq.heappop(heap)
print(heap)
1
2
[10, 14]
[14]
1
2
3
N = 5
distance = [float('inf')] * (N + 1)
distance
1
[inf, inf, inf, inf, inf, inf]
1
2
visted = [[] for _ in range(N + 1)]
visted
1
[[], [], [], [], [], []]
1
2
3
heap = []
heapq.heappush(heap, [0, 1])
heap
1
[[0, 1]]
1
2
3
4
5
6
7
distance[1] = 0
while heap:
cost, node = heapq.heappop(heap)
for c, n in visted[node]:
if cost + c < distance[n]:
distance[n] = cost + c
heapq.heappush(heap, [cost + c, n])
1
dis
1
[inf, 0, inf, inf, inf, inf]
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
# 2개의 마을에 대한 거리정보가 2개 이므로, 정리가 필요함
# ex) [마을, 마을, 거리] -> [거리, 마을]
# 방문 정보를 넣을 리스트 생성
# 아래 처럼 만들면, 안쪽 리스트가 모두 같은 id값을 가지게 되어, 하나만 변경해도 모두가 변경되게 됨
# visited = [[]] * (N + 1)
# list를 comprehension으로 생성해야, 리스트안의 리스트가 각기 다른 id를 가지게됨
visited = [[] for i in range(N + 1)]
# [[], [], [], [], [], []]
# road = [마을1, 마을2, 거리]
for r in road:
# 마을1 정보에 대한 거리를 (거리, 도착 마을)로 설정
visited[r[0]].append([r[2], r[1]])
# 마을2 정보에 대한 거리를 (거리, 도착 마을)로 설정
visited[r[1]].append([r[2], r[0]])
# [[], 0번 마을
# [[1, 2], [2, 4]], 1번 마을, 2번 마을로가는데 1의 거리, 4번 마을로 가는데 2의 거리
# [[1, 1], [3, 3], [2, 5]],
# [[3, 2], [1, 5]],
# [[2, 1], [2, 5]],
# [[2, 2], [1, 3], [2, 4]]]
1
visited
1
2
3
4
5
6
[[],
[[1, 2], [2, 4]],
[[1, 1], [3, 3], [2, 5]],
[[3, 2], [1, 5]],
[[2, 1], [2, 5]],
[[2, 2], [1, 3], [2, 4]]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 전체 마을에 대한 거리 초기 설정 (모두 inf), 처음 시작인 0번 마을은 없기 떄문에 +1을 해줌
distance = [float('inf')] * (N + 1)
# heap 시작 설정 1번 마을로 가는 거리는 0
heap = []
heapq.heappush(heap, [0, 1])
# 1번 마을의 거리 설정 -> 0
distance[1] = 0
# heap이 비기 전까지
while heap:
# heap에서 맨 앞에(루트)
cost, node = heapq.heappop(heap)
# 방문지의 cost, node
for c, n in visited[node]:
# 방문지의 cost와 현재 cost를 더 한게 거리의 합보다 낮으면 갱신
if cost + c < distance[n]:
distance[n] = cost + c
heapq.heappush(heap, [cost + c, n])
1
2
for c, n in visited[1]:
print(c, n)
1
len([dis for dis in distance if k >= dis])
1
1
1
2
for c, n in visited[1]:
print(c, n)
1
2
1 2
2 4