배달

배달
Summer/Winter Coding(~2018) 
768명 완료

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

다익스트라 알고리듬을 이용하는 거 같은데.. 
다익스트라 알고리듬이 기억이 안 난다 ㅠ,.ㅠ

일단 생각의 흐름을 따라 코딩했다..

테스트 케이스는 통과가 되지만...
당연히 순서가 꼬이면... 엉망인 답이 나온다..

문제는 순서~!

def solution(n, road, k):
    distances = {1: 0}
    for index, (a, b, length) in enumerate(road):
        distances[b] = min(distances.get(a, float('inf')) + length, distances.get(b, float('inf')))
        distances[a] = min(distances[b] + length, distances.get(a, float('inf')))
        # print(distances)
    return len([1 for a in distances.values() if a <= k])


print(solution(5, [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]], 3))
print(solution(5, [[2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2], [1, 2, 1]], 3))

{1: 0, 2: 1}
{1: 0, 2: 1, 3: 4}
{1: 0, 2: 1, 3: 4, 5: 3}
{1: 0, 2: 1, 3: 4, 5: 3, 4: 2}
{1: 0, 2: 1, 3: 4, 5: 3, 4: 2}
{1: 0, 2: 1, 3: 4, 5: 3, 4: 2}
4
{1: 0, 3: 2000, 2: 2000}
{1: 0, 3: 2000, 2: 2000, 5: 2000}
{1: 0, 3: 2000, 2: 2000, 5: 2000, 4: 2}
{1: 0, 3: 2000, 2: 2000, 5: 2000, 4: 2}
{1: 0, 3: 2000, 2: 2000, 5: 4, 4: 2}
{1: 0, 3: 2000, 2: 1, 5: 4, 4: 2}
3

다익스트라가 가까운 노드부터 탐색하던 개념이던가...
예전에 책에서 본 적 있는데...

알고리듬 책은 Hello Coding 그림으로 개념을 이해하는 알고리즘 - 아디트야 바르가바 추천. 
고등학교 때 퀵 정렬 공부한 이후로 전혀 알고리듬을 공부하지 않았던 아재 취미 코더에게도 어렵지 않았다...
(뒷광고 아님, 리뷰용 책 한 권 받아본 적 없음.)

def solution(n, road, k):
    graph = {}
    for a, b, cost in road:
        graph[a] = graph.get(a, set()).union({(b, cost)})
        graph[b] = graph.get(b, set()).union({(a, cost)})
    distances = {1: 0}
    while graph:
        node, min_val = None, float('inf')
        for key in distances:
            if key in graph and distances[key] < min_val:
                node, min_val = key, distances[key]
        for neighbor, cost in graph[node]:
            if neighbor in graph:
                distances[neighbor] = min(distances[node] + cost, distances.get(neighbor, float('inf')))
        del graph[node]
    return sum(1 for a in distances.values() if a <= k)

테스트 1 〉	통과 (0.07ms, 10.9MB)
테스트 2 〉	통과 (0.06ms, 10.7MB)
테스트 3 〉	통과 (0.07ms, 10.8MB)
테스트 4 〉	통과 (0.08ms, 10.7MB)
테스트 5 〉	통과 (0.09ms, 10.8MB)
테스트 6 〉	통과 (0.05ms, 10.7MB)
테스트 7 〉	통과 (0.07ms, 10.8MB)
테스트 8 〉	통과 (0.06ms, 10.8MB)
테스트 9 〉	통과 (0.06ms, 10.9MB)
테스트 10 〉	통과 (0.07ms, 10.8MB)
테스트 11 〉	통과 (0.07ms, 10.8MB)
테스트 12 〉	통과 (0.17ms, 10.7MB)
테스트 13 〉	통과 (0.12ms, 10.7MB)
테스트 14 〉	통과 (3.02ms, 11.2MB)
테스트 15 〉	통과 (4.55ms, 11.6MB)
테스트 16 〉	통과 (0.09ms, 10.8MB)
테스트 17 〉	통과 (0.12ms, 10.8MB)
테스트 18 〉	통과 (0.69ms, 10.9MB)
테스트 19 〉	통과 (3.46ms, 11.5MB)
테스트 20 〉	통과 (0.62ms, 10.8MB)
테스트 21 〉	통과 (5.58ms, 12.4MB)
테스트 22 〉	통과 (0.91ms, 10.9MB)
테스트 23 〉	통과 (4.82ms, 12MB)
테스트 24 〉	통과 (2.97ms, 11.4MB)
테스트 25 〉	통과 (7.16ms, 13.3MB)
테스트 26 〉	통과 (6.91ms, 13.3MB)
테스트 27 〉	통과 (7.17ms, 13.5MB)
테스트 28 〉	통과 (7.55ms, 13.6MB)
테스트 29 〉	통과 (7.29ms, 13.5MB)
테스트 30 〉	통과 (5.63ms, 13.5MB)
테스트 31 〉	통과 (0.18ms, 10.8MB)
테스트 32 〉	통과 (0.25ms, 10.8MB)

생각의 흐름에 따라 코딩했더니..
일반적인 다익스트라 스타일과 좀 다른 느낌이라..

공부 차원에서...
일반적인 다익스트라 스타일도...
찾아서 코딩해 보았다...

def solution(N, road, K):
    from queue import PriorityQueue
    distances = [float('inf') for _ in range(N + 1)]
    distances[1] = 0
    que = PriorityQueue()
    que.put((0, 1))
    while not que.empty():
        distance, node = que.get()
        if distance > distances[node]:  # 없어도 작동은 하지만.. 속도를 위해..
            continue
        for a, b, cost in road:
            if a == node:
                next_dist = cost + distance
                if next_dist < distances[b]:
                    distances[b] = next_dist
                    que.put((next_dist, b))
            elif b == node:
                next_dist = cost + distance
                if next_dist < distances[a]:
                    distances[a] = next_dist
                    que.put((next_dist, a))
    return sum(1 for d in distances if d <= K)

테스트 1 〉	통과 (0.54ms, 10.9MB)
테스트 2 〉	통과 (0.52ms, 10.8MB)
테스트 3 〉	통과 (0.49ms, 10.8MB)
테스트 4 〉	통과 (0.52ms, 10.8MB)
테스트 5 〉	통과 (0.57ms, 10.8MB)
테스트 6 〉	통과 (0.55ms, 10.8MB)
테스트 7 〉	통과 (0.53ms, 10.8MB)
테스트 8 〉	통과 (0.54ms, 10.8MB)
테스트 9 〉	통과 (0.48ms, 10.8MB)
테스트 10 〉	통과 (0.59ms, 10.8MB)
테스트 11 〉	통과 (0.57ms, 10.8MB)
테스트 12 〉	통과 (0.73ms, 10.8MB)
테스트 13 〉	통과 (0.64ms, 10.8MB)
테스트 14 〉	통과 (2.71ms, 11.1MB)
테스트 15 〉	통과 (4.07ms, 11.6MB)
테스트 16 〉	통과 (0.61ms, 10.8MB)
테스트 17 〉	통과 (0.64ms, 10.8MB)
테스트 18 〉	통과 (1.67ms, 10.9MB)
테스트 19 〉	통과 (4.58ms, 11.2MB)
테스트 20 〉	통과 (1.58ms, 10.9MB)
테스트 21 〉	통과 (5.14ms, 12.3MB)
테스트 22 〉	통과 (2.12ms, 10.8MB)
테스트 23 〉	통과 (5.77ms, 12MB)
테스트 24 〉	통과 (3.94ms, 11.3MB)
테스트 25 〉	통과 (6.73ms, 13.4MB)
테스트 26 〉	통과 (6.75ms, 13.3MB)
테스트 27 〉	통과 (6.81ms, 13.4MB)
테스트 28 〉	통과 (7.47ms, 13.6MB)
테스트 29 〉	통과 (7.01ms, 13.5MB)
테스트 30 〉	통과 (6.55ms, 13.6MB)
테스트 31 〉	통과 (0.83ms, 10.8MB)
테스트 32 〉	통과 (0.96ms, 10.8MB)

힙큐와 우선순위큐와의 속도 비교도 한번.. 

def solution(N, road, K):
    from heapq import heappush, heappop
    distances = [float('inf') for i in range(N + 1)]
    distances[1] = 0
    que = []
    heappush(que, (0, 1))
    while que:
        distance, node = heappop(que)
        if distance > distances[node]:  # 없어도 작동은 하지만.. 속도를 위해..
            continue
        for a, b, cost in road:
            if a == node:
                next_dist = cost + distance
                if next_dist < distances[b]:
                    distances[b] = next_dist
                    heappush(que, (next_dist, b))
            elif b == node:
                next_dist = cost + distance
                if next_dist < distances[a]:
                    distances[a] = next_dist
                    heappush(que, (next_dist, a))
    return sum(1 for d in distances if d <= K)

테스트 1 〉	통과 (0.05ms, 10.8MB)
테스트 2 〉	통과 (0.05ms, 10.8MB)
테스트 3 〉	통과 (0.05ms, 10.7MB)
테스트 4 〉	통과 (0.06ms, 10.9MB)
테스트 5 〉	통과 (0.07ms, 10.8MB)
테스트 6 〉	통과 (0.05ms, 10.7MB)
테스트 7 〉	통과 (0.06ms, 10.8MB)
테스트 8 〉	통과 (0.06ms, 10.8MB)
테스트 9 〉	통과 (0.04ms, 10.9MB)
테스트 10 〉	통과 (0.06ms, 10.8MB)
테스트 11 〉	통과 (0.07ms, 10.8MB)
테스트 12 〉	통과 (0.16ms, 10.8MB)
테스트 13 〉	통과 (0.11ms, 10.8MB)
테스트 14 〉	통과 (1.96ms, 11.1MB)
테스트 15 〉	통과 (2.95ms, 11.6MB)
테스트 16 〉	통과 (0.08ms, 10.9MB)
테스트 17 〉	통과 (0.10ms, 10.8MB)
테스트 18 〉	통과 (0.88ms, 10.7MB)
테스트 19 〉	통과 (3.52ms, 11.2MB)
테스트 20 〉	통과 (0.79ms, 10.8MB)
테스트 21 〉	통과 (4.15ms, 12.3MB)
테스트 22 〉	통과 (1.22ms, 10.9MB)
테스트 23 〉	통과 (4.38ms, 12MB)
테스트 24 〉	통과 (2.91ms, 10.9MB)
테스트 25 〉	통과 (5.63ms, 13.2MB)
테스트 26 〉	통과 (5.96ms, 13.3MB)
테스트 27 〉	통과 (5.41ms, 13.4MB)
테스트 28 〉	통과 (6.24ms, 13.6MB)
테스트 29 〉	통과 (5.91ms, 13.6MB)
테스트 30 〉	통과 (6.18ms, 13.5MB)
테스트 31 〉	통과 (0.20ms, 10.8MB)
테스트 32 〉	통과 (0.34ms, 10.9MB)

최댓값이 필요할 때 type이 있는 언어는 
type에 따른 최댓값을 이용하는 경우가 많은데, 
파이썬은 type이 없어서 애매하다.

이때 math.inf 나 sys.maxsize 등을 이용해도 되겠지만, 
외부 모듈을 불러와야 하는 불편함이 있어서
float('inf')를 즐겨 쓴다.