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

프로그래머스 배달 (lv. 2)

문제 설명

1~N 까지의 마을이 그래프처럼 생긴 나라가 있다.
2. 1번 마을의 음식점에서 배달을 하려고 한다.
3. 다른 마을로 배달을 갈 때는 K이하의 거리만 가려고 한다.
4. 그래프의 간선과 비용, N, K가 주어질 때, 배달을 갈 수 있는 마을의 개수를 구해보자

접근 방법

그래프의 한점에서 다른 점들로의 최소비용이면은 다익스트라 알고리즘으로 구현하면 쉽게 풀릴 것 간다.

문제 유의점

• a, b를 연결하는 여러개의 도로 존재 가능

구현 방법

• 다익스트라를 표현하는 리스트가 필요하다. [0, 0, inf, ...]
• 비용이 있는 그래프를 표현할 방법이 필요하다.
• 재귀 중, 왔던 길로 다시 돌아가지 않게 해야한다.

코드

d = [0, 0]+ [10000*2222]*50
def visit(start, g, cost):
    d[start] = cost
    for v in g[start]:
        dest, cost = v
        if d[start] + cost < d[dest]:
            visit(dest, g, d[start]+cost)

def solution(N, road, K):
    answer = 0
    g = {}
    for v in road:
        if v[0] not in g:
            g[v[0]] = []
        g[v[0]].append((v[1],v[2]))

        if v[1] not in g:
            g[v[1]] = []
        g[v[1]].append((v[0],v[2]))

    visit(1, g, 0)
    answer = sum([1 for x in d[1:] if x <= K])
    return answer

시행착오 및 보완점

• 중복을 피하기 위해 visited 사용해봤는데 실패
  - 다익스트라 알고리즘은 최소값을 만들기 위해 다시 방문하는 일이 있을 수 있음을 바로 생각하지 못하고 visited를 썼다.
• 논리적으로 쉽게 풀기위해 cost인자를 넣었지만
  visit전에 d[dest]를 바꿔주면 cost인자를 빼도 된다.