[백준] 31937 로그프레소 마에스트로 (Javascript)

문제

BOJ31937_로그프레소 마에스트로

풀이

문제 정의

N개의 컴퓨터가 있고 각각 1~N까지의 번호가 매겨진다. 이 컴퓨터들은 서로 파일을 주고 받고, 파일을 주고 받은 기록은 로그로 기록된다. 각각의 로그에는 "파일을 보낸 시각, 보낸 컴퓨터의 번호, 받은 컴퓨터의 번호" 가 담겨있다.

이때, 특정 컴퓨터가 바이러스에 감염되었다면 그 컴퓨터가 전송한 파일을 받은 컴퓨터도 바이러스에 감염된다.
입력으로 M개의 로그와, 감염된 컴퓨터들의 번호가 주어졌을 때, 이를 토대로 맨 처음에 감염된 컴퓨터를 찾는 문제다.

또한 답이 유일한 경우만 입력으로 주어진다.

5 3 2
1 2
1 2 1
2 1 2
3 4 5

예를 들어 위 입력값은 답이 1일수도, 2일수도 있으므로 입력으로 주어지지 않는다.

해결방안

처음엔 그래프 탐색 문제라고 생각했다.
컴퓨터들이 노드고, 파일 전송 로그를 이용해서 간선을 만들어서 역방향으로 탐색해주며 풀려고 했지만 코드를 작성할수록 너무 복잡해졌다.

그래서 시간을 두고 나중에 다시 봤는데 완전탐색으로 풀 수 있을 것 같았다.

i번 컴퓨터를 가장 먼저 감염된 컴퓨터라고 가정하고, 파일 전송 로그를 시간 순서대로 정렬한 뒤 로그의 순서대로 감염을 수행시켜준다.

감염을 모두 수행했다면 현재 감염된 컴퓨터들의 번호와 입력으로 주어진 감염된 컴퓨터들의 번호가 일치한다면 i번째 컴퓨터가 가장 먼저 감염된 컴퓨터인 것이다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, K] = input[0].split(' ').map(Number);
const arr = input[1].split(' ').map(Number);
const logs = input.slice(2).map((e) => e.split(' ').map(Number));
const visited = Array(N + 1).fill(false);
const infected = Array(N + 1).fill(false);
let answer = 0;
for (const pc of arr) {
    infected[pc] = true;
}

logs.sort((a, b) => a[0] - b[0]);

// i를 1~N까지 돌면서 가장 먼저 감염된 pc라고 가정하고, 로그의 시각 순서대로 파일 전송을 수행한다.
// 파일 전송을 모두 수행했을 때 감염된 pc와 입력으로 주어진 감염된 pc가 일치한다면 그때의 i가 정답
for (let i = 1; i <= N; i++) {
    visited[i] = true;
    for (const [t, a, b] of logs) {
        // a가 감염되었다면 b도 감염
        if (visited[a]) visited[b] = true;
    }
    let flag = true;
    for (let j = 1; j <= N; j++) {
        if (visited[j] !== infected[j]) {
            flag = false;
            break;
        }
    }
    if (flag) {
        answer = i;
        break;
    } else visited.fill(false);
}

console.log(answer);