[알고리즘] 프로그래머스 Lv2 배달

문제

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

풀이과정

문제를 보자마자 "이건 가중치 무방향 그래프다!" 생각이 들었다.
뒤에 알고리즘은 MST일까, 다익스트라일까 두근두근

코드를 작성할 때는 MST라고 생각하지 못하고 BFS인데, 최소 시간만 담도록 해야지. 생각했는데, 풀고보니 MST인 듯 하다.

주어진 road 리스트를 사용하여 가중치를 담은 인접 행렬을 만들었다.
이때, 두 마을 간 도로는 여러 개가 존재할 수 있다는 점이 함정이었다.
그래서 인접 행렬의 초기 값을 inf로 하고 최소값을 담도록 코딩하였다.

인접 행렬을 만든 다음에는 visitied 행렬을 만들었고 초기 값은 -1로 해주었다. false로 하니 시작점 방문처리가 어려웠기 때문이다. 그러나 다시 생각해보니, 시작 마을은 항상 1로 고정이기 때문에 1은 방문했다고 치면 되는 것이었다...

다음으로는 BFS 방식 코드를 작성하였다.
두 마을 간 도로가 있으면서, (현재까지의 시간 + 도로 이동 시간)이 가려는 도시에 해당하는 visited 칸에 담긴 값보다 작거나 같으면 queue에 넣는 방식으로 작성하였다.

그 후, 0부터 K까지의 수가 visited에 몇 개나 있는지 센 값을 answer로 구하였다.

코드

# 프로그래머스 배달

def solution(N, roads, K):
    adj_arr = [[float("inf")] * (N+1) for _ in range(N+1)]
    for road in roads:
        # 무방향 그래프
        adj_arr[road[0]][road[1]] = min(road[2], adj_arr[road[0]][road[1]])
        adj_arr[road[1]][road[0]] = min(road[2], adj_arr[road[1]][road[0]])

    visited = [-1] * (N+1)
    queue = [1]
    visited[1] = 0

    while queue:
        now = queue.pop(0)
        for next in range(2, N+1):
            if now != next and adj_arr[now][next] != float("inf"):
                if visited[next] != -1 and visited[next] < visited[now] + adj_arr[now][next]:
                    continue

                visited[next] = visited[now] + adj_arr[now][next]
                queue.append(next)

    # print(visited)
    answer = 0
    for i in range(K+1):
        answer += visited.count(i)
    return answer


N = 5
roads = [[1,2,1], [2,3,3], [5,2,2], [1,4,2], [5,3,1], [5,4,2]]
K = 3

N = 6
roads = [[1,2,1], [1,3,2], [2,3,2], [3,4,3], [3,5,2], [3,5,3], [5,6,1]]
K = 4

print(solution(N, roads, K))

다른 사람의 풀이

def solution(N, road, K):
    visited = [False] * (N + 1)
    costs = [float('inf')] * (N + 1)
    costs[1] = 0
    parents = [1]          
    while (parents):
        parent = parents.pop(0)
        visited[parent] = True
        for a, b, cost in road:
            if (a == parent or b == parent):
                target = b if a == parent else a
                if costs[target] > costs[parent] + cost:
                    costs[target] = costs[parent] + cost
                    parents.append(target)

    return sum(1 for c in costs if c <= K)

같은 알고리즘이지만, 훨씬 간략하고 메모리를 덜 사용했으며 가독성이 좋게 작성한 것 같다.
굿...