[Python-CodingTest] Lv2. 배달

배달

문제 정리

현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

입력

N=5
road=[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]
K=3

처리 과정

출력

4

풀이

import heapq

def dijkstra(dist,adj):
    # 출발노드를 기준으로 각 노드들의 최소비용 탐색
    heap = []
    heapq.heappush(heap, [0,1])  # 거리,노드 (1번 노드(자기자신)까지는 거리 0)
    while heap:
        cost, node = heapq.heappop(heap)
        for c,n in adj[node]:
            if cost+c < dist[n]:
                # 최단거리 갱신
                dist[n] = cost+c
                heapq.heappush(heap, [cost+c,n])

def solution(N, road, K):
    dist=[float('inf')]*(N+1) # 최소거리 갱신할 리스트 (infinite로 초기화 안하고 1000 같은걸로 하면 통과하지 못하는 테스트 있음!)
    dist[1] = 0  # 1번은 자기자신이니까 거리 0
    adj = [[] for _ in range(N+1)]  # 인접노드&거리 기록할 배열 (1차원 리스트)
    cnt=0 # 배달 가능한 마을 수
    
    for r in road:
        # 양방향 통행 (r[0],r[1]: 마을 번호 / r[2]: 거리)
        adj[r[0]].append([r[2],r[1]]) # append 거리,노드
        adj[r[1]].append([r[2],r[0]])

    dijkstra(dist,adj)
    
    for x in dist:
        if x<=K:
            cnt+=1

    return cnt

정리

• print(adj)를 했을 때 결과
  

  [[], [[1, 2], [2, 4]], [[1, 1], [3, 3], [2, 5]], [[3, 2], [1, 5]], [[2, 1], [2, 5]], [[2, 2], [1, 3], [2, 4]]]
  

  adj는 [거리,노드]를 원소로 가진 1차원 리스트이다.

• 모든 테스트 케이스를 통과하기 위해서는 max값을 1000 혹은 10000으로 잡지 말고, float('inf')로 잡기!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기