[프로그래머스] 배달 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 1번 마을에서 각 마을까지 배달하는데 최소 시간을 모두 구하고 구한 최소 시간이 주어진 제한 시간 K보다 작거나 같은 마을의 개수를 세어주면 된다.

해당 문제를 해결하기 위해서 다익스트라 알고리즘을 활용한다.

다익스트라 알고리즘을 실행할 때 방문하지 않은 인접 노드를 방문하는 부분이 있는데, 이 부분에서 우선순위 큐를 사용하면 현재까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있고 더 긴 거리로 계산되었을 경우 스킵도 가능하다.

 

1. 우선순위 큐를 사용하기 위해 heapq 모듈을 불러온다. import heapq
2. 각 노드별 연결되어 있는 마을과 도로의 정보를 저장할 2차원 리스트를 생성한다. graph = [[] for _ in range(N + 1)]
3. 주어진 도로의 정보를 하나씩 불러온다. for info in road
   1. 제일 앞 데이터는 시작 마을에 대한 정보이고 start = info[0]
   2. 두 번째 데이터는 도착 마을에 대한 정보이고 end = info[1]
   3. 마지막 세 번째 데이터는 두 마을을 연결하는 도로를 지나는 데 걸리는 시간이다. time = info[2]
   4. 시작 마을과 도착 마을로 하여 연결된 마을 도로의 정보를 저장한다. graph[start].append([end, time])
   5. 도착 마을에서 시작 마을로도 올 수 있으므로 반대 정보도 저장한다. graph[end].append([start, time])
4. 다익스트라 알고리즘을 함수로 표현한다. def dijkstra(graph, start)
   1. 각 마을까지의 배달 시간을 저장할 리스트를 생성하고 무한대 값으로 초기화한다. times = [float('inf') for _ in range(N + 1)]
   2. 처음 출발 마을의 시간을 0으로 저장한다. times[start] = 0
   3. 우선순위 큐를 사용할 큐 자료구조를 생성한다. queue = []
   4. 시작 마을부터 탐색을 하기 위해 큐 자료구조에 출발 마을에서의 시간, 출발 마을 번호를 리스트로 묶어 넣어준다. heapq.heappush(queue, [times[start], start])
   5. 만약 큐 자료구조에 노드가 없을 때까지 반복한다. while (queue)
      1. 현재 배달 시간과 현재 도착한 마을 위치를 각 큐에서 가져온다. current_time, current_end = heapq.heappop(queue)
      2. 만약 현재 도착한 마을에 저장된 최소 배달 시간이 현재 배달 시간보다 작으면 현재 최소 시간이 잘 저장되어 있는 상태이므로 그대로 두고 넘어간다. if (times[current_end] < current_time): continue
      3. 그게 아닐 경우 마을 도로를 저장한 정보에서 현재 도착 마을과 연결된 마을의 정보를 각각 다음 도착지와 다음 배달 시간으로 불러온다. for new_end, new_time in graph[current_end]
      4. 시간은 현재 배달 시간하고 다음 도착지로 배달했을 때 걸리는 시간을 더한 값으로 저장하고 time = current_time + new_time
      5. 만약 새로 계산된 시간이 다음 도착지의 최소 배달 시간보다 작으면 if (time < times[new_end])
      6. 다음 도착지의 최소 배달 시간을 새로 계산된 시간으로 수정한다. times[new_end] = time
      7. 그리고 큐에 새로 계산된 시간과 다음 도착지를 리스트로 묶어 추가한다. heapq.heappush(queue, [time, new_end])
   6. 최종적으로 각 마을까지 최소 배달 시간이 저장된 리스트를 반환한다. return times
5. 결과를 저장할 변수를 생성하고 다익스트라 알고리즘을 적용한 결과를 저장한다. result = dijkstra(graph, 1)
6. 배달 시간이 저장된 결과를 하나씩 불러오며 for i in result
   1. 만약 해당 값이 지정된 배달 제한 시간보다 같거나 작으면 (배달 가능하면) 배달 가능한 마을의 수를 1 증가시켜 준다. if (i <= K): answer += 1
      

3. 소스코드

import heapq

def solution(N, road, K):
    answer = 0

    graph = [[] for _ in range(N + 1)]
    for info in road:
        start = info[0]
        end = info[1]
        time = info[2]

        graph[start].append([end, time])
        graph[end].append([start, time])
        
    def dijkstra(graph, start):
        times = [float('inf') for _ in range(N + 1)]
        times[start] = 0
        queue = []
        heapq.heappush(queue, [times[start], start])

        while (queue):
            current_time, current_end = heapq.heappop(queue)

            if (times[current_end] < current_time):
                continue
            
            for new_end, new_time in graph[current_end]:
                time = current_time + new_time
                if (time < times[new_end]):
                    times[new_end] = time
                    heapq.heappush(queue, [time, new_end])
            
        return times

    result = dijkstra(graph, 1)
    for i in result:
        if (i <= K):
            answer += 1

    return answer