[프로그래머스/파이썬] 배달

문제 출처- https://programmers.co.kr/learn/courses/30/lessons/12978

 

처음 이 문제를 보자마자 이건 딕셔너리에 {출발지: [(도착지, 시간), (도착지, 시간), ...], 출발지: [...], ...} 이런식으로 우선 풀어서, 재귀로 누적 시간을 잰다음 K보다 시간이 작은지 체크하고 list에 넣어야겠다 라고 생각하고 이렇게 풀었다.

 

 

def solution(N, road, K):
    towns = [500000] * (N+1)
    graph = collections.defaultdict(list)

    for r in road:
        a, b, time = r
        graph[a].append((b, time))
        graph[b].append((a, time))

    def go_delivery(visited: list, arrive: int, time: int):
        for a, t in graph[visited[-1]]:
            if a == arrive and time+t <= K:
                towns[arrive] = min(towns[arrive], time+t)

            elif a not in visited and time+t <= K:
                visited_a = visited[:]
                visited_a.append(a)
                go_delivery(visited_a, arrive, time+t)

    answer = 1
    for i in range(2, N+1):
        go_delivery([1], i, 0)
        if towns[i] <= K:
            answer += 1

    print(towns)

    return answer

1. towns= [500000] * (N+1) 인 이유는 거리의 최대값 조건이 500,000 미만이어서 지정했고, 뒤에서 min으로 비교해 최소거리를 조정할 생각이다. N+1은 넣을 때마다 인덱스를 -1 하고 싶지 않아서 이렇게 설정하였다.

 

 

2. 이제 하나하나 딕셔너리 형식으로 넣는다. 이 로직을 수행하면 이렇게 결과가 나온다.

 

문제 예 - road : [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]

반복문 수행 후 - 

{

    1: [(2, 1), 

        (3, 2)], 

    

    2: [(1, 1), 

        (3, 2)], 

    

    3: [(1, 2), 

        (2, 2), 

        (4, 3), 

        (5, 2), 

        (5, 3)], 

    

    4: [(3, 3)], 

    

    5: [(3, 2), 

        (3, 3), 

        (6, 1)], 

    

    6: [(5, 1)]

}

 

3. 어차피 1은 0이니가 answer에 1로 초기화한 상태에서 2부터 6 (2,3,4,5,6) 까지 반복문을 돌았다. 

각각을 목적지로 삼고, 1부터 2, 1부터 3, 1부터 4, 1부터 5, 1부터 6 이런식으로 간다. 그래서 1부터 4에서는 1이 바로 4로 가는 것이 없으니 3을 먼저 간다음 4로 갈 수 있도록 했다. 

근데 여기서 visited가 없다면 서로를 호출하는 무한 루프에 빠지기 때문에 visited로 경유지를 list 형태로 넘겨주어 한번 경유한 곳은 다시 되돌아가지 않는 식으로 했다.

 

그렇게 하여 문제에 나온 예제의 답이 잘 나왔고 채점을 해보았다.

두근두근...

 

하지만 테스트 한개가 계속 점점점으로 내 불안함을 증폭시키더니... (오래 걸린다는 것은 언제나 불길한 예감을 준다..)

 

 

...ㅠㅠ

 

결국 검색을 해보니 다들 다익스트라 알고리즘으로 풀었다는 것이다. 그래서 다익스트라 알고리즘을 찾아보니 딱 이 문제는 다익스트라 알고리즘이었고, (다익스트라 설명 예제풀이만 봐도 내가 풀고 있는 문제풀이와 겹쳐...) 그것도 우선순위 큐를 사용해서 풀면 시간이 세이브 된다는 사실을 알았다.

 

그래서 참고 예제를 활용하여 풀었다.

 

 

def solution2(N, road, K):
    graph = collections.defaultdict(list)

    for a, b, time in road:
        graph[a].append((b, time))
        graph[b].append((a, time))

	# (시간, 정점)
    Q = [(0, 1)]
    visited = collections.defaultdict(int)

    while Q:
        time, to = heapq.heappop(Q)

        if to not in visited:
            visited[to] = time
            frm = to

            for to, t in graph[frm]:
                alt = time + t
                heapq.heappush(Q, (alt, to))

    return sum(1 for n, t in visited.items() if t <= K)

 

graph에 넣는 것은 이전에 내가 했던 방식이 맞았고, 다른 점은 우선순위 큐를 사용한다는 점, 경유지 리스트는 dict로 관리하는 점에서 달랐다. 이전 문제 풀이에서 towns에 인덱스로 찾아서 집어넣었는데 dict로 하니 지저분하게 N+1해서 할 필요는 없어서 좋았다.

 

(시간, 정점)으로 시간이 먼저 나온 이유는 우선순위 큐에서 큐에서 가장 적게 걸리는 시간부터 먼저 나오라고 graph와서는 순서가 바뀐것이다. 여기서 heapq에 들어가는 (시간, 정점) 중에 시간은 누적시간이 들어가게 된다.

 

to에서 frm으로 굳이 한번 갈아주는 이유는 가독성 때문인데... 잘 머르게따...

 

힙에서 하나씩 꺼내서 if 문으로 방문하면 그냥 넘어가게 되어 있는데 이유는 한번 방문한 곳은 이미 우선순위 큐에서 가장 적은 시간 걸리는 순으로 시간을 저장했기 때문이다. 

 

그다음 sum으로 간략하게 계산하여 리턴했다.

 

그랬더니 이제서야 통과가 나왔다.. (기분좋은 파란색...)

 

이제 잘수있겠다..... ^_ㅠ

 

 

 

 

참고 풀이: [책] 파이썬 알고리즘 인터뷰