12908 텔레포트 3

문제

수빈이는 크기가 무한대인 격자판 위에 살고 있다. 격자판의 각 점은 두 정수의 쌍 (x, y)로 나타낼 수 있다.

제일 처음에 수빈이의 위치는 (xs, ys)이고, 집이 위치한 (xe, ye)로 이동하려고 한다.

수빈이는 두 가지 방법으로 이동할 수 있다. 첫 번째 방법은 점프를 하는 것이다. 예를 들어 (x, y)에 있는 경우에 (x+1, y), (x-1, y), (x, y+1), (x, y-1)로 이동할 수 있다. 점프는 1초가 걸린다.

두 번째 방법은 텔레포트를 사용하는 것이다. 텔레포트를 할 수 있는 방법은 총 세 가지가 있으며, 미리 정해져 있다. 텔레포트는 네 좌표 (x1, y1), (x2, y2)로 나타낼 수 있으며, (x1, y1)에서 (x2, y2)로 또는 (x2, y2)에서 (x1, y1)로 이동할 수 있다는 것이다. 텔레포트는 10초가 걸린다.

수빈이의 위치와 집의 위치가 주어졌을 때, 집에 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 xs와 ys가, 둘째 줄에 xe, ye가 주어진다. (0 ≤ xs, ys, xe, ye ≤ 1,000,000,000)

셋째 줄부터 세 개의 줄에는 텔레포트의 정보 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000,000)

입력으로 주어지는 모든 좌표 8개는 서로 다르다.

====

문제 분석

16958 텔레포트 문제와 똑같은 유형이다.

모든 좌표를 distance에 넣을 것이며 어떠한 점 s에서 출발해서 e까지 가는데 중간에 지점들을 거칠 때 얻을 수 있는 최소 거리를 구하면 된다. 

각 노드의 좌표값을 x,y라고 할 때 좌표를 담은 배열에는 텔레포트가 가능한 좌표들끼리 알려주기 위해 [s,x,y] 를 배열에 담을 것이다.

우선 출발점 도착점부터 넣는다.

const coordinate = [
        [0, sx, sy],
        [1, ex, ey],
];

이후 중간 텔레포트 좌표들도 담아준다.

for (let i = 0; i < 3; i++) {
    const [x, y, xx, yy] = teleports[i];
    coordinate.push([i + 2, x, y]);
    coordinate.push([i + 2, xx, yy]);
}

우선 i에서 j 까지 직선 거리를 담아준다.

const distance = Array.from({ length: n }, () =>
        Array.from({ length: n }).fill(INF)
);
const cal = (x, y, xx, yy) => Math.abs(x - xx) + Math.abs(y - yy);
    
for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (i === j) distance[i][i] = 0;
            else {
                const [t, x, y] = coordinate[i];
                const [t1, x1, y1] = coordinate[j];

                let temp = cal(x, y, x1, y1);
                if (t === t1) {
                    temp = Math.min(10, temp);
                }
                distance[i][j] = temp;
                distance[j][i] = temp;
            }
        }
}

 

이제 폴로이드 알고리즘을 넣어준 뒤 출발 지점을 뜻하는 좌표 배열에서의 인덱스 0 과 도착 지점 인덱스 1의 최소 거리인 distance[0][1] 을 출력해준다.

for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = i; j < n; j++) {
                const temp = Math.min(
                    distance[i][j],
                    distance[i][k] + distance[k][j]
                );

                distance[i][j] = temp;
                distance[j][i] = temp;
            }
        }
    }
console.log(distance[0][1]);

 

정답 코드

const main = (sx, sy, ex, ey, teleports) => {
    const n = 8;
    const INF = 2_000_000_000;
    const distance = Array.from({ length: n }, () =>
        Array.from({ length: n }).fill(INF)
    );
    const cal = (x, y, xx, yy) => Math.abs(x - xx) + Math.abs(y - yy);
    
    const coordinate = [
        [0, sx, sy],
        [1, ex, ey],
    ];
    

    for (let i = 0; i < 3; i++) {
        const [x, y, xx, yy] = teleports[i];
        coordinate.push([i + 2, x, y]);
        coordinate.push([i + 2, xx, yy]);
    }

    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (i === j) distance[i][i] = 0;
            else {
                const [t, x, y] = coordinate[i];
                const [t1, x1, y1] = coordinate[j];

                let temp = cal(x, y, x1, y1);
                if (t === t1) {
                    temp = Math.min(10, temp);
                }
                distance[i][j] = temp;
                distance[j][i] = temp;
            }
        }
    }

    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = i; j < n; j++) {
                const temp = Math.min(
                    distance[i][j],
                    distance[i][k] + distance[k][j]
                );

                distance[i][j] = temp;
                distance[j][i] = temp;
            }
        }
    }
    console.log(distance[0][1]);
};

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

const [sx, sy] = input[0].split(' ').map((v) => +v);
const [ex, ey] = input[1].split(' ').map((v) => +v);

const tels = input.slice(2).map((v) => v.split(' ').map((v) => +v));

main(sx, sy, ex, ey, tels);