Level 2. 배달

배달

코딩테스트 연습 > Summer,Winter Coding(~2018) > 배달

https://programmers.co.kr/learn/courses/30/lessons/12978

---

문제 설명

1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다. 마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

Input value =

• int(N): number of nodes

• list(road): list(distance between start node and next node)

• int(K): limit distance

Process = Using dijkstra

Output value = number of nodes satisfied distance < K

---

문제 구상

Deque 이용

from collections import deque

1. 시작 노드를 제외한 나머지를 inf로 지정(시작 노드 = 0)

nodes = dict()
dist = {i:float('inf') if i != 1 else 0 for i in range(1, N+1)}

2. 입력된 road(시작노드,방문노드,거리)를 이용하여 노드 구성

for v1, v2, d in road:
    nodes[v1] = nodes.get(v1, []) + [(v2, d)]
    nodes[v2] = nodes.get(v2, []) + [(v1, d)]

3. 탐색 위치 지정

que = deque([1])

4. 시작 노드부터 방문하지 않은 인접 노드를 방문하여 거리 계산

while que:
    cur_node = que.popleft() # 시작 노드 추출
    for nxt_node, d in nodes[cur_node]: # 시작노드와 연결된 노드와 거리 확인
        if dist[nxt_node] > dist[cur_node] + d: # 시작노드와 연결 노드와의 거리의 합이 연결 노드의 최종 거리보다 작으면
            dist[nxt_node] = dist[cur_node] + d # 해당 값을 갱신
            que.append(nxt_node) # 다음 노드를 탐색하기 위해 시작 노드 갱신

5. dist값 중 K 보다 작은 것의 갯수 return

len([i for i in dist.values() if i <= K])

Heapq 이용

import heapq

1. 시작 노드를 제외한 나머지를 inf로 지정(시작 노드 = 0)

total_distance = {node: float('inf') if node!=1 else 0 for node in range(1,N+1)}

2. 노드 구성
   • 단, 해당 문제에서는 road값이 (시작노드,방문노드,거리) 임을 고려

nodes = dict()
for start,destination,distance in road:
    nodes[start] = nodes.get(start,[])+[(destination,distance)] # 시작 노드와 도착 노드의 관계
    nodes[destination] = nodes.get(destination,[])+[(start,distance)] # 도착 노드와 시작 노드의 관계

3. 탐색 시작 위치 지정

queue = []
heapq.heappush(queue, 1)

4. 시작 노드부터 방문하지 않은 인접 노드를 방문하여 거리 계산

while queue:
    now_node = heapq.heappop(queue) # 시작 노드 추출
    for next_node, next_distance in nodes[now_node]: # 시작노드와 연결된 노드와 거리 확인
        if total_distance[next_node] > total_distance[now_node]+next_distance: # 시작노드와 연결 노드와의 거리의 합이 연결 노드의 최종 거리보다 작으면
            total_distance[next_node] = total_distance[now_node]+next_distance # 해당 값을 갱신
            heapq.heappush(queue,next_node) # 다음 노드를 탐색하기 위해 시작 노드 갱신

5. Total_distance의 값 중 K 보다 작은 것의 갯수

len([d for d in total_distance.values() if d <= K])

---

전체 코드

Deque

from collections import deque

def solution(N, road, K):
    nodes = dict()
    dist = {i:float('inf') if i != 1 else 0 for i in range(1, N+1)}
    for v1, v2, d in road:
        nodes[v1] = nodes.get(v1, []) + [(v2, d)]
        nodes[v2] = nodes.get(v2, []) + [(v1, d)]
    que = deque([1])
    while que:
        cur_node = que.popleft()
        for nxt_node, d in nodes[cur_node]:
            if dist[nxt_node] > dist[cur_node] + d:
                dist[nxt_node] = dist[cur_node] + d
                que.append(nxt_node)
    return len([i for i in dist.values() if i <= K])

# Code test
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)

Heapq

import heapq
def solution(N, road, K):
    total_distance = {node: float('inf') if node!=1 else 0 for node in range(1,N+1)}
    nodes = dict()
    for start,destination,distance in road:
        nodes[start] = nodes.get(start,[])+[(destination,distance)]
        nodes[destination] = nodes.get(destination,[])+[(start,distance)]
    queue = []
    heapq.heappush(queue, 1)
    while queue:
        now_node = heapq.heappop(queue)
        for next_node, next_distance in nodes[now_node]:
            if total_distance[next_node] > total_distance[now_node]+next_distance:
                total_distance[next_node] = total_distance[now_node]+next_distance
                heapq.heappush(queue,next_node)
    return len([d for d in total_distance.values() if d <= K])

# Code test
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)