[알고리즘/백준/1325] 효율적인 해킹(BFS, JavaScript, 백준 Nodejs로 풀 때 유의사항)

문제

 

---

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

풀이

---

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
    this.tail = 0;
  }
  push(item) {
    this.data[this.tail++] = item;
  }
  pop() {
    this.head++;
  }
  front() {
    return this.data[this.head];
  }
  rear() {
    return this.data[this.tail - 1];
  }
  isEmpty() {
    return this.head === this.tail;
  }
  size() {
    return Math.abs(this.head - this.tail);
  }
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m] = N.split(" ").map(Number);
let pairs = arr.map((row) => row.split(" ").map(Number));

let graph = Array.from({ length: n + 1 }, () => []);
let hacked = Array.from({ length: n + 1 }, () => 0);

for (let [s, e] of pairs) {
  graph[e].push(s);
}

// 각 노드에서 해킹할 수 있는 컴퓨터 수 세기
for (let i = 1; i <= n; i++) {
  const ch = Array.from({ length: n + 1 }, () => 0);
  const q = new Queue();
  let cnt = 1;
  let max = Number.MIN_SAFE_INTEGER;

  ch[i] = 1;
  q.push(i);

  while (!q.isEmpty()) {
    const v = q.front();
    q.pop();

    for (let i = 0; i < graph[v].length; i++) {
      const nv = graph[v][i];
      if (ch[nv] === 0) {
        ch[nv] = 1;
        cnt += 1;
        q.push(nv);
      }
    }
  }

  hacked[i] = cnt;
}

const maxVal = Math.max(...hacked);
const bestOptions = hacked
  .map((num, idx) => (num === maxVal ? idx : -1))
  .filter((num) => num > 0);

console.log(bestOptions.join(" "));

DFS로 풀어도, BFS로 풀어도 계속해서 시간 초과, 출력 초과라는 오류가 생겨서 고생했던 문제이다.

N이 10,000이상으로 클 때는 BFS로 푸는 것이 좋다고 하는데, BFS로 풀어도 시간 초과가 나는 건 shift 때문이었다.

 

Node.js로 백준 문제를 풀 때는 for문 내부에서 console을 찍거나 shift, pop을 사용했을 때 원본 배열의 값을 가져오면서 수정하기 때문에 시간이 훨씬 오래 걸린다고 한다. 따라서 시간 초과가 발생할 수 있다.

 

이를 해결하기 위해 Queue 자료구조를 따로 만들어 활용하는 방법이 있다. shift() 대신 front()로 가장 먼저 들어온 값을 조회하고, 시작 인덱스를 하나 증가시켜주는 방식을 활용한다.

 

풀이는 시작점이 여러 개라는 부분을 빼면 일반적인 BFS 문제였다. 1~n의 각 노드에서 시작해 인접 리스트(graph)를 탐색하면서 이동 가능한 노드 수를 hacked 배열에 저장한다. 이후 이동 가능한 노드의 최댓값과 같은 경우, 해당 인덱스를 map, filter를 통해 추출한다. 그리고 join을 통해 배열을 문자열로 변환한다.

 

Node.js로 알고리즘 풀 때 주의할 사항들은 아래 내용을 참고해보자. 

 

https://hanch-dev.tistory.com/4

[백준] Node.js 알고리즘 풀때 주의 사항