[백준] 12908 텔레포트 3 (Javascript)

문제

BOJ12908_텔레포트 3

풀이

각각의 (x, y)좌표를 하나의 노드로, 총 8개의 노드로 간주할 수 있고, 노드간의 거리는 기본적으로 $|x1 - x2| + |y1 - y2|$ 이고, 예외적으로 텔레포트 할 수 있는 좌표 끼리는 거리를 10으로 고정한다.

예를 들어 입력이 아래와 같이 주어졌다고 가정해보자.

3 7
10000 30000
3 10 5200 4900
12212 8699 9999 30011
12200 8701 5203 4845

그렇다면 각각의 좌표는 아래와 같이 총 8개의 노드로 나타낼 수 있다.

[
  [ 3, 7 ],
  [ 10000, 30000 ],
  [ 3, 10 ],
  [ 5200, 4900 ],
  [ 12212, 8699 ],
  [ 9999, 30011 ],
  [ 12200, 8701 ],
  [ 5203, 4845 ]
]

이를 토대로 모든 노드간의 거리를 구해주고

const dist = Array.from({ length: 8 }, () => Array(8).fill(Infinity));

// 거리 테이블 초기화
for (let i = 0; i < 8; i++) {
    for (let j = 0; j < 8; j++) {
        if (i === j) {
            dist[i][j] = 0;
            continue;
        }
        dist[i][j] = Math.abs(arr[i][0] - arr[j][0]) + Math.abs(arr[i][1] - arr[j][1]);
        dist[j][i] = Math.abs(arr[i][0] - arr[j][0]) + Math.abs(arr[i][1] - arr[j][1]);
    }

텔레포트로 갈 수 있는 노드간의 거리는 10으로 고정해준다.

// 텔레포트로 갈 수 있는 좌표는 거리를 10으로 설정
for (let i = 1; i <= 3; i++) {
    dist[i * 2][i * 2 + 1] = 10;
    dist[i * 2 + 1][i * 2] = 10;
}

그런 다음 플로이드 워셜 알고리즘을 수행해줘서 모든 노드간의 최단 거리를 구한다.

// 플로이드 워셜
for (let k = 0; k < 8; k++) {
    for (let i = 0; i < 8; i++) {
        for (let j = 0; j < 8; j++) {
            if (dist[i][j] > dist[i][k] + dist[k][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

그런 다음 우리가 최종적으로 구하고자 했던 0번 노드에서 1번 노드로 가는 최단거리를 출력한다.

console.log(dist[0][1]);

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const arr = [];
arr.push(input.shift().split(' ').map(Number));
arr.push(input.shift().split(' ').map(Number));
for (let i = 0; i < 3; i++) {
    const row = input[i].split(' ').map(Number);
    arr.push(row.splice(0, 2));
    arr.push(row.splice(0, 2));
}

const dist = Array.from({ length: 8 }, () => Array(8).fill(Infinity));

// 거리 테이블 초기화
for (let i = 0; i < 8; i++) {
    for (let j = 0; j < 8; j++) {
        if (i === j) {
            dist[i][j] = 0;
            continue;
        }
        dist[i][j] = Math.abs(arr[i][0] - arr[j][0]) + Math.abs(arr[i][1] - arr[j][1]);
        dist[j][i] = Math.abs(arr[i][0] - arr[j][0]) + Math.abs(arr[i][1] - arr[j][1]);
    }
}

// 텔레포트로 갈 수 있는 좌표는 거리를 10으로 설정
for (let i = 1; i <= 3; i++) {
    dist[i * 2][i * 2 + 1] = 10;
    dist[i * 2 + 1][i * 2] = 10;
}

// 플로이드 워셜
for (let k = 0; k < 8; k++) {
    for (let i = 0; i < 8; i++) {
        for (let j = 0; j < 8; j++) {
            if (dist[i][j] > dist[i][k] + dist[k][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

console.log(dist[0][1]);