[프로그래머스] 배달

문제 설명

1부터 N까지 N개의 마을이 있다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있다. 어떤 마을에서 다른 마을로 이동할 때 걸리는 시간이 주어지고, 음식을 배달할 수 있는 최대 시간 K가 주어진다. 마을 간 이동시간 정보 road와 최대 시간 K가 주어졌을 때 1번 마을에서 배달할 수 있는 마을의 수를 구하는 문제다.

문제 풀이

처음 시도했던 방법은 가중치 양방향 그래프를 DFS를 통해서 완전탐색하는 방법을 선택했지만 32번 테스트 케이스에서 시간 초과가 발생했다. 결과적으로는 플로이드-워셜 알고리즘으로 각 마을 간의 최단 시간을 구해서 그 시간이 K 이하인 경우를 구하는 방법으로 문제를 해결했다.

먼저, 각 마을 간의 이동 시간을 저장할 2차원 배열을 생성하고 값을 Infinity로 초기화했다. 그리고 주어진 road 배열을 순회하면서 직접 이동할 수 있는 마을 간의 이동 시간을 저장했다. 케이스 중에서 직접 이동할 수 있는 경로가 여러 개인 경우도 있기 때문에 값이 작은 것으로 할당해주어야 했다.

그리고 플로이드-워셜 알고리즘을 사용해서 중간 경로를 통해서 이동할 수 있는 최단거리로 사전에 생성했던 2차원 배열을 업데이트 해주었다.

마지막으로 1번 마을에서 배달할 수 있는 마을의 수를 체크하기 위해서 2차원 배열에서 1번 마을에서 K 시간 이하로 걸리는 마을의 수를 카운트한 뒤에 정답을 출력했다.

function solution(N, road, K) {
  	// 마을 간의 이동 시간 2차원 배열 생성
    const g = Array.from({length: N+1}, () => Array(N+1).fill(Infinity))
	// road 배열을 순회하면서 직접 이동할 수 있는 이동 시간을 2차원 배열에 저장
    for (const [a,b,c] of road) {
        g[a][b] = g[a][b] === Infinity ? c : Math.min(g[a][b],c)
        g[b][a] = g[b][a] === Infinity ? c : Math.min(g[b][a],c)
    }
  	// 중간 경로를 통해 이동할 수 있는 최단거리로 2차원 배열을 업데이트
    for (let i = 1; i <= N; i++) {
        for (let j = 1; j <= N; j++) {
            for (let k = 1; k <= N; k++) {
                g[j][k] = Math.min(g[j][k], g[j][i] + g[i][k])
            }
        }
    }
  	// 1번 마을은 1번 마을로 배달할 수 있다.
    let answer = 1
    // 1번 마을의 이동 시간 정보를 2번 마을부터 N번 마을까지 순회하면서 배달할 수 있는 마을의 수를 카운트 한다.
    for (let i = 2; i <= N; i++) {
        if (g[1][i] <= K) {
            answer++
        }
    }
    return answer
}

출처: 프로그래머스 - 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978
알고리즘, 플로이드-워셜(Floyd-Warshall) 알고리즘 https://chanhuiseok.github.io/posts/algo-50/