프로그래머스
1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수 구하기.
- N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다.
- 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다.
- 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다.
- 마을의 개수 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 이하입니다.
- 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
입출력
| 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 |
접근 방식
한 지점에서 다른 모든 지점까지의 최단 경로를 구해 K이하인 것의 개수를 구한다.
📌 다익스트라 알고리즘
: 한 지점에서 다른 모든 지점까지의 최단경로를 계산
단계마다 방문하지 않은 노드 중 가장 최단 거리가 짧은 노드를 선택한 후 그 노드를 거쳐가는 경우를 확인하여 최단거리를 갱신한다. -----> 우선순위 큐 사용
각각의 경우에 가장 짧은 것을 선택한다는 점에서 그리디 알고리즘, 해당 노드까지의 최단거리를 기록한다는 점에서 다이나믹 프로그래밍의 성격을 가짐.
코드
import heapq
def dks(v, graph, dp):
q = []
# 현재 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐 사용
heapq.heappush(q, (0, 1)) #cost, start
dp[1] = 0
while q:
# 현재 정점까지의 비용 : cost
w, n = heapq.heappop(q)
# 현재 정점까지의 비용 + 현재 정점에서 다음 정점까지의 비용 c = 다음 노드 까지의 비용
for ad_n, ad_w in graph[n]:
ww = w + ad_w
# 다음 노드까지의 비용이 기록된 값보다 작으면 조건 성립
if ww < dp[ad_n]:
dp[ad_n] = ww#업데이트
heapq.heappush(q, (ww, ad_n))
return dp
def solution(N, roads, K):
ans = 0
graph = [[] for _ in range(N+1)]
# 양방향
for start, end, time in roads:
graph[start].append((end, time))
graph[end].append((start, time))
# N번 노드까지 오는 비용
dp = [1e9]*(N+1)
result = dks(1, graph, dp)
for re in result:
if re <= K:
ans += 1
return ans-
graph
연결 관계를 저장할 2차원 리스트인 graph에 노드와 걸리는 시간 순으로 저장한다. 이 때 양방향 도로이므로 양방향 관계로 저장한다.
-
dp
각 노드까지의 최단 거리를 저장할 dp테이블을 만들고 매우 큰 수인1e9로 초기화한다.
-
다익스트라 알고리즘
각 상황에서 길이가 최소인 노드를 찾기 위해 우선순위 큐 자료구조를 이용한다. heapq 모듈을 이용해 구현한다.- 각 상황에서 최단 거리를 뽑아내기 위해 최소힙으로 구현된 힙에 (거리, 노드) 순서로 push한다.
또한 시작 노드의 dp테이블을 0으로 초기화한다.
- 현재 노드
: 우선순위 큐가 비어있지 않을 동안, 힙에서 pop한 원소의 cost(현재 노드까지의 비용), node(현재 노드 정보)에서 cost가 node의 dp테이블에 적힌 비용보다 크다면 무시한다(이미 탐색 완료). 그것이 아니라면 이웃노드를 탐색한다. ---> 최단거리라면 cost와 dp[node]의 값이 같을 것이다.
- 이웃 노드(연결 노드)
: 현재 노드와 이어진 노드들을 탐색한다.
현재 노드를 거쳐서 이웃 노드로 가는 비용이 dp[이웃노드]보다 작다면 dp[이웃노드]를 갱신하고 힙에 (갱신한 비용, 이웃노드)를 넣는다.
- 최종 dp테이블을 반환하고 각 원소 중 K이하인 원소의 개수를 반환한다.
- 각 상황에서 최단 거리를 뽑아내기 위해 최소힙으로 구현된 힙에 (거리, 노드) 순서로 push한다.
