[프로그래머스] 배달 (Python)

문제 링크

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

프로그래머스

 

문제 설명

1부터 N까지 번호가 하나씩 부여되어 있는 나라가 있다. 각 마을은 양방향으로 통행할 수 있는 도로가 있고, 

서로 다른 마을 간에 이 도로를 지나 이동한다. 현재 1번 마을에 있는 음식점에서 각 마을로 배달을 하려고 한다.

N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을의 수를 return하는 문제이다.

제한사항

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수) 는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b는 도로가 연결하는 두 마을의 번호이며, c는 도로를 지나는데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

 

❌ Code - 실패

def solution(N, road, K):
    answer = 0
    
    dis = [0] * (N + 1)
    for r1, r2, d in road:
        a, b = min(r1, r2), max(r1, r2)
        if not dis[b]:
            dis[b] = dis[a] + d
        else:
            dis[b] = min(dis[b], dis[a] + d)
    
    for d in dis:
        if d != 0 and d <= K:
            answer += 1
    
    return answer + 1

 

문제를 너무 쉽게 생각하였다. 양방향도 고려하지 않았고,

출발지 a에서 이동 거리를 더한 값과 도착지 b의 값의 최소값만 고려를 해서 여러 마을을 거쳐가는 것을 고려하지 않게 된다.  

 

반례 ) input : 5, [[1, 2, 4], [1, 3, 1], [3, 4, 1], [4, 2, 1], [2, 5, 1]], 4 / output : 5

 

여러 마을을 거쳐 최단 경로를 찾기 위해 플로이드 워셜 알고리즘을 사용하게 되었다.

점화식은 D(i , j) = min(D(i , j) , D(i , k) + D(k , j)) 가 된다.

 

✅ Code - 성공

def solution(N, road, K):
    
    dis = [[float('inf')] * (N + 1) for _ in range(N + 1)]    
    
    for r1, r2, d in road:
        dis[r1][r2] = min(dis[r1][r2], d)
        dis[r2][r1] = min(dis[r2][r1], d)
    
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    
    answer = 0
    dis[1][1] = 0
    for n1 in dis[1]:
        if n1 <= K:
            answer += 1
    
    return answer

 

※ 참고

1번 마을에서 1번 마을로 가는 것은 이동 거리가 0이기 때문에, 

플로이드 워셜 사용 후, 1번 마을의 값은 0으로 초기화 해주어야 한다.