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

문제 정리

• 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다.

• 도로를 지날 때 걸리는 시간은 도로별로 다릅니다.

• 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다.

• 다음은 N = 5, K = 3인 경우의 예시입니다.

  

  위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다.

  그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다.

  따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.

문제 해결 방법

한 정점에서 다른 정점까지 최단경로를 구하면 된다.

이런 문제를 해결하는 알고리즘이 존재한다 바로 플로이드 와샬 알고리즘이다.

→ 플로이드 와샬 알고리즘

플로이드 와샬 알고리즘을 활용해서 1번에서 갈 수 있는 모든 정점을 찾으면 된다.

마을 개수가 1이상 50이하의 자연수이므로 플로이드 와샬 알고리즘으로 해결이 가능하다.

코드

• click

코드 설명

1. INF는 이동 불가능한 경우를 나타낸다.
   • K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하라고 했다.
     • 그래서 500001로 넣어줬다. 어차피 500000을 넘으면 이동 가능한 경로에서 제외된다.
     • 그러나 사실 큰 수를 아무거나 넣어줘도 상관 없다.