17182 우주 탐사선 (자바스크립트)

문제

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

입력

첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)

다음 N 줄에 걸쳐 각 행성 간 이동 시간 Tij 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij  ≤ 1000)

출력

모든 행성을 탐사하기 위한 최소 시간을 출력한다.

===

문제 풀이

출발점부터 시작하여 모든 노드를 방문하는 가장 짧은 거리를 찾아면 된다.

또한 중복 방문이 가정하다는 전제가 있으므로 입력에서 주어진 i에서 j까지의 거리를 더 적은 비용으로 찾아갈 수 있는지 판별하기 위해 플루이드 알고리즘으로 i->m->j 를 찾아본다.

const [n, k] = input[0].split(' ').map(Number);
const gr = input.slice(1).map((s) => s.split(' ').map(Number));

for (let m = 0; m < n; m++) {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            gr[i][j] = Math.min(gr[i][j], gr[i][m] + gr[m][j]);
        }
    }
}

이후 비트마스크와 dfs를 통해 모든 경로를 방문하는 가장 짧은 거리를 구하면 된다.

const dp = Array.from({ length: n }, () => Array(1 << n).fill(Infinity));

function dfs(cur, visited) {
    if (visited === (1 << n) - 1) return 0;
    if (dp[cur][visited] !== Infinity) return dp[cur][visited];

    for (let next = 0; next < n; next++) {
        if (visited & (1 << next)) continue;
        const nextVisited = visited | (1 << next);
        const cost = gr[cur][next] + dfs(next, nextVisited);
        dp[cur][visited] = Math.min(dp[cur][visited], cost);
    }

    return dp[cur][visited];
}

console.log(dfs(k, 1 << k));