프로그래머스 12978 배달 파이썬 풀이

난이도 : Lv. 2
풀이일 : 2412043
https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

---

문제

---

아이디어

• 다익스트라 알고리즘을 구현한다.
• 1번 마을에서 다익스트라 함수를 실행하여 K 시간 내로 배달 가능한 마을의 숫자를 answer에 센다.
• answer를 출력한다.

---

1차 전체 풀이 코드

import heapq

def solution(N, road, K):
    answer = 0
    route = [[] for _ in range(N + 1)]
    
    def djikstra(start):
        count = 0
        visited = [int(1e9)] * (N + 1)
        visited[start] = 0
        queue = []
        heapq.heappush(queue, [0, start])
        
        # 최소 시간 탐색
        while queue:
            cost, now = heapq.heappop(queue)
            if cost <= visited[now]:
                for add, after in route[now]:
                    if visited[after] > cost + add:
                        visited[after] = cost + add
                        heapq.heappush(queue, [cost + add, after]) 
        
        # 배달 가능한 마을 수 세기
        for i in range(N):
            if visited[i + 1] <= K:
                count += 1
                
        return count
    
    # 입력처리
    for a, b, c in road:
        route[a].append([c, b])
        route[b].append([c, a])
    
    # 1번 마을에서 배달 가능한 마을 수 구하기
    answer += djikstra(1)
    
    return answer

---

상세 풀이 코드

import heapq

def solution(N, road, K):
    answer = 0
    route = [[] for _ in range(N + 1)]

• import heapq : 우선순위 큐를 사용할 것이기 때문에 heapq를 import 해준다.
• answer : 1번 마을에서 K 시간 내로 배달 가능한 마을의 수를 셀 변수
• route : 각 마을 사이를 이어주는 길 정보 저장

 

    def djikstra(start):
        count = 0
        visited = [int(1e9)] * (N + 1)
        visited[start] = 0
        queue = []
        heapq.heappush(queue, [0, start])

• 다익스트라 함수의 변수들
• count : start 마을에서 K 시간 내로 배달이 가능한 마을의 숫자를 셀 변수
• visited : start 마을에서 각 마을까지 배달하는 데에 걸리는 시간을 저장할 1차원 배열. 초기 값은 매우 큰 값으로 설정
• visited[start] = 0 : 현재 마을까지 걸리는 시간은 0이므로 재할당
• queue : 우선순위큐로 사용할 배열
• heqpq를 사용하여 queue 배열에 [현재 마을까지의 비용, 현재 마을 번호]를 추가

 

        # 최소 시간 탐색
        while queue:
            cost, now = heapq.heappop(queue)
            if cost <= visited[now]:
                for add, after in route[now]:
                    if visited[after] > cost + add:
                        visited[after] = cost + add
                        heapq.heappush(queue, [cost + add, after])

• queue 가 있는동안 반복을 수행
• cost, now : 힙큐로 사용하는 queue에서 cost가 작은 값을 우선적으로 뽑아 할당.
  • cost : now까지 이동하는 데에 사용한 총 비용
  • now : 현재 마을의 번호
• if cost <= visited[now] : 현재 이동 비용이 이미 visited[now] 위치에 기록되어 있는 최소값보다 작다면 다음 작업 수행
• for 반복문 : 현재 마을 now와 연결된 마을들까지의 이동비용 add, 도착마을 after에 대해 반복 수행
• if visited[after] > cost + add : 현재 경로를 거쳐 after 마을에 도착하는 비용이 이미 기록된 after마을 방문의 최소값보다 작다면 다음 작업 수행
  • after 마을 방문의 최소값을 수정하고 우선순위큐에 다음 마을 정보 추가

 

        # 배달 가능한 마을 수 세기
        for i in range(N):
            if visited[i + 1] <= K:
                count += 1
                
        return count

• 일반적인 다익스트라 문제에서는 필요하지 않지만, 문제의 조건에 따라 추가한 부분
• 출발 마을 start에서 K 시간 내로 배달이 가능한 마을의 개수를 센다.
• 전체 마을에 대한 최소값이 저장된 배열을 순회하며 K 시간 내로 배달이 가능한 마을을 세 count 변수에 저장
• count 반환

 

    # 입력처리
    for a, b, c in road:
        route[a].append([c, b])
        route[b].append([c, a])
    
    # 1번 마을에서 배달 가능한 마을 수 구하기
    answer += djikstra(1)
    
    return answer

• for 반복문 : 입력으로 주어진 road 정보로 양방향 길 정보 저장해주는 작업
• answer에 djikstra(1)을 실행하여 1번 마을에서 출발해 K 시간 내로 배달할 수 있는 마을의 수를 추가
• 최종 answer 리턴

---

2차 풀이 코드

import heapq

def solution(N, road, K):
    answer = 0
    route = [[] for _ in range(N + 1)]
    
    def djikstra(start):
        nonlocal answer
        visited = [int(1e9)] * (N + 1)
        visited[start] = 0
        queue = []
        heapq.heappush(queue, [0, start])
        
        # 최소 시간 탐색
        while queue:
            cost, now = heapq.heappop(queue)
            if cost <= visited[now]:
                for add, after in route[now]:
                    if visited[after] > cost + add:
                        visited[after] = cost + add
                        heapq.heappush(queue, [cost + add, after]) 
        
        # 배달 가능한 마을 수 세기
        for i in range(N):
            if visited[i + 1] <= K:
                answer += 1
                
        return
    
    # 입력처리
    for a, b, c in road:
        route[a].append([c, b])
        route[b].append([c, a])
    
    # 1번 마을에서 배달 가능한 마을 수 구하기
    djikstra(1)
    
    return answer

수정 이유

• answer를 djikstra 함수에서 직접 수정하고 싶었는데 에러가 발생해 우선 1차 풀이 방법으로 풀었었다. 이전에 리스트는 중첩 함수 내에서 수정했던 기억이 있어서 answer를 직접 수정하기 위해 수정 방법을 찾아보았다.

 
수정 내용

• djikstra 함수 내 nonlocal answer 추가, count 변수 삭제
• count 변수 삭제에 따라 return 시 반환값 삭제, 함수 호출 부분 수정

---

최종 풀이 코드

import heapq

def solution(N, road, K):
    route = [[] for _ in range(N + 1)]
    
    def djikstra(start):
        answer = 0
        visited = [int(1e9)] * (N + 1)
        visited[start] = 0
        queue = []
        heapq.heappush(queue, [0, start])
        
        # 최소 시간 탐색
        while queue:
            cost, now = heapq.heappop(queue)
            if cost <= visited[now]:
                for add, after in route[now]:
                    if visited[after] > cost + add:
                        visited[after] = cost + add
                        heapq.heappush(queue, [cost + add, after]) 
        
        # 배달 가능한 마을 수 세기
        for i in range(N):
            if visited[i + 1] <= K:
                answer += 1
                
        return answer
    
    # 입력처리
    for a, b, c in road:
        route[a].append([c, b])
        route[b].append([c, a])
    
    # 1번 마을에서 배달 가능한 마을 수 구하기
    return djikstra(1)

수정 이유

• 이 문제에서는 1번 마을에서 출발해 K 시간 내로 배달 가능한 마을의 수를 정하게 주어졌지만, 함수 자체는 다른 어떤 마을이 주어져도, 또 여러 마을에 대해 여러번 함수를 호출해도 제 기능을 해야하지 않나 하는 생각이 들었다.
• answer를 바로 수정해버리면 특정한 경우에만 이 함수를 쓸 수 있어 재사용성이 낮은 나쁜 코드가 아닌가 싶어서 수정했다.

 
수정 내용

• answer의 선언 위치를 djikstra 함수 내로 이동하고 반환값에 answer를 추가한다.
• 이 문제에서는 1번 마을에서의 결과만 반환하면 되므로 solution의 return에 djikstra(1)을 넣었다.

---

느낀점

• global은 자주 사용했는데, nonlocal을 처음 써봤다. 관련 내용을 정리해봐야지.
• 그리고 역시 이전에 푼 코드 어디 고칠 데 없나 살펴보는게 재밌다. 처음부터 잘 짜고 싶은데 잘안돼!