16958 텔레포트 (자바스크립트)

문제

2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다.

두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자.

입력

첫째 줄에 도시의 수 N, 텔레포트하는데 걸리는 시간 T가 주어진다.

둘째 줄부터 N개의 줄에 도시의 정보를 의미하는 세 정수 s, x, y가 1번 도시부터 N번 도시까지 순서대로 주어진다. s가 1인 경우에는 특별한 도시라는 의미이고, 0인 경우는 특별한 도시가 아니라는 의미이다. (x, y)는 도시의 좌표이다.

다음 줄에는 M이 주어지고, 다음 M개의 줄에는 두 도시 A와 B가 주어진다. 

출력

총 M개의 줄에 걸쳐서 A에서 B에 가는 최소 이동 시간을 출력한다.

=====

문제 분석

그래프 좌표 위에 있는 도시들이 있고 테스트케이스에 있는 시작 도시부터 도착 도시까지의 최단 거리를 출력하면 되는 문제이다.

bfs나 dfs를 통해 좌표 하나하나 이동해가면서 좌표를 알아보고 중간중간 텔레포트끼리 연결 된 도시라면 또 이동하는 로직을 짤 수 있겠지만 이럴 경우 bfs를 테스트케이스만큼 돌려야하니 굉장히 비효율적이다.

따라서 출발 도시에서부터 도착 도시까지 갈 때 중간에 다른 도시들을 돌면서 최소 거리를 알아 낼 수 있는 폴로이드 알고리즘을 사용했다.

( i 에서 j 까지의 거리 ) = ( i 에서 j 까지의 거리 ) 와 ( i에서 k까지 가고+ k에서 j 까지 가는 거리) 중 최솟값

const INF = 1_000_000_000;
    const distance = Array.from({ length: n + 1 }, () =>
        Array.from({ length: n + 1 }, () => INF)
    );

    const cal = (sx, sy, ex, ey) => Math.abs(ex - sx) + Math.abs(ey - sy);

    for (let i = 0; i < n; i++) {
        const [ss, sx, sy] = coordinate[i];
        for (let j = i; j < coordinate.length; j++) {
            if (i === j) {
                distance[i + 1][j + 1] = 0;
            } else {
                const [es, ex, ey] = coordinate[j];
                if (ss === 1 && es === 1) {
                    const temp = Math.min(t, cal(sx, sy, ex, ey));
                    distance[i + 1][j + 1] = temp;
                    distance[j + 1][i + 1] = temp;
                } else {
                    const temp = cal(sx, sy, ex, ey);
                    distance[i + 1][j + 1] = temp;
                    distance[j + 1][i + 1] = temp;
                }
            }
        }
    }

정답 코드

const main = (n, t, coordinate, m, answer) => {
    const result = [];
    const INF = 1_000_000_000;
    const distance = Array.from({ length: n + 1 }, () =>
        Array.from({ length: n + 1 }, () => INF)
    );

    const cal = (sx, sy, ex, ey) => Math.abs(ex - sx) + Math.abs(ey - sy);

    for (let i = 0; i < n; i++) {
        const [ss, sx, sy] = coordinate[i];
        for (let j = i; j < coordinate.length; j++) {
            if (i === j) {
                distance[i + 1][j + 1] = 0;
            } else {
                const [es, ex, ey] = coordinate[j];
                if (ss === 1 && es === 1) {
                    const temp = Math.min(t, cal(sx, sy, ex, ey));
                    distance[i + 1][j + 1] = temp;
                    distance[j + 1][i + 1] = temp;
                } else {
                    const temp = cal(sx, sy, ex, ey);
                    distance[i + 1][j + 1] = temp;
                    distance[j + 1][i + 1] = temp;
                }
            }
        }
    }
    for (let k = 1; k < n + 1; k++) {
        for (let i = 1; i < n + 1; i++) {
            for (let j = i + 1; j < n + 1; j++) {
                const temp = Math.min(
                    distance[i][j],
                    distance[i][k] + distance[k][j]
                );
                distance[i][j] = temp;
                distance[j][i] = temp;
            }
        }
    }

    for (const [s, e] of answer) {
        result.push(distance[s][e]);
    }
    console.log(result.join('\n'));
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, t] = input[0].split(' ').map((v) => +v);
const coordinate = input
    .slice(1, n + 1)
    .map((v) => v.split(' ').map((v) => +v));

const m = +input[n + 1];
const answer = input.slice(n + 2).map((v) => v.split(' ').map((v) => +v));

main(n, t, coordinate, m, answer);