[JS] 프로그래머스 - 배달

문제링크

정답 코드

function solution(N, road, K) {
    const village = Array.from(Array(N + 1), () => Array(N + 1).fill(0));
    
    road.forEach((v) => {
        village[v[0]][v[1]] = village[v[0]][v[1]] ? Math.min(v[2], village[v[0]][v[1]]) : v[2];
        village[v[1]][v[0]] = village[v[1]][v[0]] ? Math.min(v[2], village[v[1]][v[0]]) : v[2];
    });
    
    function dfs(i, n) {
        
        for (let k = 2; k < N + 1; k ++) {
            if (village[i][k]) {
                if (!village[1][k]) {
                    village[1][k] = village[i][k] + n;
                    dfs(k, village[1][k]);
                } else {
                    if (village[1][k] > n + village[i][k]) {
                        village[1][k] = n + village[i][k];
                        dfs(k, village[1][k]);
                    }
                }
            }
        }
    }
    
    for (let i = 2; i < N + 1; i ++) {
        if (village[1][i]) {
            dfs(i, village[1][i]);
        };
    };
    
    return village[1].filter((v) => v <= K).length - 1;
}

DFS를 사용해서 풀었습니다. 처음에 문제푸는 아이디어가 생각이 안나서 고민을 많이 했지만 계속 다방면으로 생각하다보니 풀 수 있었습니다.

풀이 방법

문제를 푸는 핵심 아이디어는 마을 1에서 다른 마을로 이동할 때, 그 경로가 가장 짧을 경우에만 확정시켜줘야합니다.

마을 1에서 마을2까지 이동하는 직선 경로의 길이가 위의 예시에서는 1이고 제일 짧지만 다른 경우가 있을 수 있습니다.

예를 들어, 마을 1에서 마을 2까지의 직선 경로의 길이가 10인데 마을 1과 마을 3의 경로가 2이고 마을 3의 경로와 마을 2의 경로가 2일 경우 합이 5로 제일 작기 때문입니다. 마을 1과 임의의 마을로 가는 경로가 가장 짧은게 아니라면 계속 탐색을 해주어야합니다.

문제 예시로 풀이방법을 설명해보도록 하겠습니다.

    const village = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

먼저 길의 길이를 나타낼 village라는 배열을 하나 만들어줍니다. 배열은 0부터 시작이기 때문에 쉽게 코드를 구현하기 위해 N + 1까지 만들어서 마을 번호를 문제에서 제시한 그대로 표현했습니다.

    road.forEach((v) => {
        village[v[0]][v[1]] = village[v[0]][v[1]] ? Math.min(v[2], village[v[0]][v[1]]) : v[2];
        village[v[1]][v[0]] = village[v[1]][v[0]] ? Math.min(v[2], village[v[1]][v[0]]) : v[2];
    });

주어진 road를 순회하면서 마을 사이의 길의 길이를 village 배열에 넣습니다.
여기서 주의해야 할 것은 마을과 마을을 이어주는 길은 여러개가 될 수 있다라는 문제의 조건입니다.

이 조건을 만족시켜주기 위해서 village 배열에 길의 길이를 입력할 때, 만약 이미 길의 길이가 있다면 현재 길의 길이 값과 비교해서 작은 값을 넣어주었습니다. 잘 이해가 안되시는 분들은 아래 그림을 참고하시면 됩니다.

위 그림을 보시면 3번 5번 마을을 이어주는 길이 2개가 있습니다. 위의 경우를 해결하기 위해서입니다.

그리고 양방향으로 설정을 해줘야지 dfs로 탐색할 때, 끝까지 탐색이 가능합니다.

    for (let i = 2; i < N + 1; i ++) {
        if (village[1][i]) {
            dfs(i, village[1][i]);
        };
    };

마을 1번부터 출발이므로 village[1]을 순회하면서 길이 있는 마을을 dfs 함수의 첫번째 매개변수로 전달하고 두번째 매개변수에는 길의 길이를 전달합니다.

    function dfs(i, n) {
        
        for (let k = 2; k < N + 1; k ++) {
            if (village[i][k]) {
                if (!village[1][k]) {
                    village[1][k] = village[i][k] + n;
                    dfs(k, village[1][k]);
                } else {
                    if (village[1][k] > n + village[i][k]) {
                        village[1][k] = n + village[i][k];
                        dfs(k, village[1][k]);
                    }
                }
            }
        }
    }

이제 dfs 함수에는 다음 탐색할 마을 정보를 받아서 경로가 있을 경우 조건에 따라 처리합니다. (아래코드 참고)

if (village[i][k])

만약에 현재까지 탐색했을 때, 마을 1부터 다음 마을 정보가 아직 없을 경우 = (!village[1][k]) 마을 1부터 다음 마을의 길이를 더해주어서 넣어줍니다. 아직 최소 경로가 아니기 때문에 dfs를 통해 더 탐색을 해줍니다. (아래코드 참고)

village[1][k] = village[i][k] + n;
dfs(k, village[1][k]);

그리고 이미 경로 정보가 있을 경우, 현재 경로가 최소 경로인지 확인하기 위해 이미 입력된 경로 길이와 비교해줍니다. (아래코드 참고)

if (village[1][k] > n + village[i][k]) {
  village[1][k] = n + village[i][k];
  dfs(k, village[1][k]);
}

만약에 이미 입력된 경로 길이가 더 긴 경우만 현재 경로의 길이로 바꿔주고 다시 탐색해줍니다.
이렇게 되면 현재 경로의 길이가 짧은 경우에만 계속 탐색을 하게 되고 모든 탐색이 끝나면 종료됩니다.

return village[1].filter((v) => v <= K).length - 1;

마지막으로는 마을 1에서 임의의 마을로 가는 경로 중에 K보다 작은 경우만 filter 함수를 통해 걸러줍니다. -1을 해주는 이유는 처음에 N + 1로 해주어서 마을 0의 정보(존재하지 않는)가 존재하기 때문입니다.