프로그래머스 - 배달 (Javascript)

문제링크

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

아이디어

 1) 1번 마을에서 각 마을로 갈 수 있는 최단 시간을 저장하기 위한 배열 dp 선언

 2) 인접행렬(map)을 만들어 문제의 input으로 주어진 road를 통해 가중치 그래프 구현.

 3) 구현한 인접행렬을 이용하여 K시간 이내에 1번 마을에서 갈 수 있는 최대 마을 수를 구함 (dfs)

  3-1) dfs 함수는 인접행렬에서 탐색하려하는 행의 인덱스 (idx, 즉 마을)와 각 마을을 거쳐오면서 소요된 시간의 합 (sum)을 인자로 받음.

  3-2) idx번째의 행 (특정 마을)을 탐색하면서 마을이 연결되어 있으면서 (time > 0) 현재 마을이동 시간과 소요된 시간의 합이 K 보다 작은 경우(newSum <= K) 조건문으로 분기

  3-3) 3-2를 만족시키는 경우에서, 아직 그 마을은 방문한 적 없거나 (dp[i] === 0) 이미 방문했지만, 현재 이동하고있는 루트가 더 적은 시간이 걸릴 경우 (dp[i] > newSum) dp를 갱신

  3-4) dp 갱신 후 다시 다음 행 재귀적으로 탐색

 4) dfs행이 끝나면 dp배열이 채워지고, dp 배열이 0보다 큰경우는 1번 마을에서 탐색할 수 있는 경우이므로 0보다 큰경우를 카운팅 한것이 수가 답이 됨.

function solution(N, road, K) {
    const dp = Array(N).fill(0);
    const map = Array.from(Array(N), () => Array(N).fill(0))
    road.forEach((val) => {
        if (map[val[0] - 1][val[1] - 1] === 0 || map[val[0] - 1][val[1] - 1] > val[2]) {
            map[val[0] - 1][val[1] - 1] = val[2];
            map[val[1] - 1][val[0] - 1] = val[2];   
        }
    })
    const dfs = (idx, sum) => {
        for (let i = 1; i < N; i++) {
            const time = map[idx][i];
            const newSum = time + sum;
            if (time > 0 && newSum <= K) {
                if (dp[i] === 0 || newSum < dp[i]) {
                    dp[i] = newSum;
                    dfs(i, newSum);
                }
            }
        }
    }
    dfs(0, 0)
    
    return dp.reduce((acc, cur) => {
                if (cur > 0) return acc + 1;
                return acc
            }, 1)
}