[백준] 1613 역사 (Javascript)

문제

BOJ1613_역사

풀이

요구사항

역사적 사건들이 일어난 날짜의 전후관계가 입력으로 주어진다.
이를 기반으로 특정 사건 두 개가 입력으로 들어왔을 때, 두 사건의 전후관계를 출력하시오.

해결방안

이 문제는 플로이드 워셜 알고리즘을 사용해서 풀 수 있다.

우선 2차원 배열을 만들고 0으로 초기화한다.
그리고 이미 알고 있는 두 사건에 대한 전후관계를 2차원 배열에 저장한다.

1 2
2 3

예를 들어 이미 알고 있는 두 사건의 전후관계가 위와 같이 입력되었다고 가정했을 때, 2차원 배열에는 아래와 같이 저장할 수있다.

arr[1][2] = -1;
arr[2][1] = 1;

arr[2][3] = -1;
arr[3][2] = 1;

이렇게 하면 두 사건의 전후관계가 배열에 저장된다.
예를 들어 1번과 2번의 전후관계를 알고싶다면, arr[1][2]의 값을 출력하면 -1이 출력되므로 1번이 2번보다 전에 일어난 사건이라는 것을 알 수 있다.

하지만 이대로 코드를 작성할 경우 1번과 3번의 전후관계를 제대로 알 수 없다.

위 입력에서는 1번이 2번보다 빠르고, 2번이 3번보다 빠르기 때문에 1번이 3번보다 빠르다.
따라서 1번과 3번의 전후관계를 출력하면 -1이 출력되어야 한다.

하지만 arr[1][3]에는 0이 저장되어 있으므로 0이 출력된다.

이를 해결하기 위해 플로이드 워셜 알고리즘을 사용할 수 있다.

for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            // i, j 사건에 대한 전후 관계가 직접 나와있지 않은 경우
            if (arr[i][j] === 0) {
                // i가 k보다 빠르고, k가 j보다 빠르면, i는 j보다 빠르다
                if (arr[i][k] === 1 && arr[k][j] === 1) arr[i][j] = 1;
                // i가 k보다 느리고, k가 j보다 느리면, i는 j보다 느리다
                else if (arr[i][k] === -1 && arr[k][j] === -1) arr[i][j] = -1;
            }
        }
    }
}

위와 같이 플로이드 워셜 알고리즘을 사용하면 직접 입력으로 주어지지 않은 전후 관계도 알 수 있다.

예를 들어 arr[1][3] === 0이기 때문에 아래의 조건을 확인한다.

if(arr[1][2] === 1 && arr[2][3] === 1) arr[1][3] = 1;

위 코드의 의미는 1번이 2번보다 빠르고, 2번이 3번보다 빠르면 1번은 3번보다 빠르다. 라는 의미이다.

이렇게 플로이드 워셜 알고리즘으로 3단 논법을 구현하면, 직접 주어지지 않은 전후관계에 대해서도 알 수 있다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [n, k] = input[0].split(' ').map(Number);
const cases = input.slice(1, 1 + k).map((e) => e.split(' ').map(Number));
const s = +input[1 + k];
const query = input.slice(1 + k + 1, 1 + k + 1 + s).map((e) => e.split(' ').map(Number));
const arr = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
let answer = '';

for (const [a, b] of cases) {
    arr[a][b] = -1; // a가 먼저오는 경우 -1
    arr[b][a] = 1; // b가 먼저오는 경우 1
}

for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            // i, j 사건에 대한 전후 관계가 직접 나와있지 않은 경우
            if (arr[i][j] === 0) {
                // i가 k보다 빠르고, k가 j보다 빠르면, i는 j보다 빠르다
                if (arr[i][k] === 1 && arr[k][j] === 1) arr[i][j] = 1;
                // i가 k보다 느리고, k가 j보다 느리면, i는 j보다 느리다
                else if (arr[i][k] === -1 && arr[k][j] === -1) arr[i][j] = -1;
            }
        }
    }
}

for (const [a, b] of query) {
    answer += arr[a][b] + '\n';
}

console.log(answer.trimEnd());