백준 18405번 경쟁적 전염 JavaScript 풀이 [BFS]

백준 18405번 경쟁적 전염 문제를 자바스크립트로 BFS 알고리즘을 이용해서 풀어보았다. 

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

 

1) 처음 시도 -> 처음 상태를 큐에 넣을 때 바이러스 번호 순서 고려가 안돼서 실패

let fs = require("fs");
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

// n x n 크기의 시험관, 1번부터 k번까지의 바이러스
let [n, k] = input[0].split(" ").map(Number);
// 시험관 정보
let graph = [];
for (let i = 1; i <= n; i++) {
  graph.push(input[i].split(" ").map(Number));
}
// s초 뒤의 (x, y)
let [s, x, y] = input[n + 1].split(" ").map(Number);

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}
// s초 뒤의 시험관의 상태
queue = new Queue();
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (graph[i][j] != 0) {
      // [바이러스 번호, 열 위치, 행 위치]
      queue.enqueue([graph[i][j], i, j]);
    }
  }
}

// s번 반복
while (s>0) {
  let queueLen = queue.getLength();
  // 1번 반복
  for (let i=0; i<queueLen; i++) {
    let node = queue.dequeue();
    let [virus, posX, posY] = node;
  
    // 상하좌우 이동
    for (let move of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
      let next = [posX + move[0], posY + move[1]];
      if (next[0] >= 0 && next[1] >= 0 && next[0] <= n - 1 && next[1] <= n - 1) {
        if (graph[next[0]][next[1]] == 0) {
          graph[next[0]][next[1]] = virus;
          queue.enqueue([virus, ...next]);
        }
      }
    }
  }
  s--;
}

console.log(graph[x-1][y-1]);

 

2) 바이러스 번호 순대로 정렬 후에 큐에 넣는 코드 삽입 후 성공!

let fs = require("fs");
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

// n x n 크기의 시험관, 1번부터 k번까지의 바이러스
let [n, k] = input[0].split(" ").map(Number);
// s초 뒤의 (x, y)
let [s, x, y] = input[n + 1].split(" ").map(Number);

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}

// 시험관 정보
let graph = [];
for (let i = 1; i <= n; i++) {
  graph.push(input[i].split(" ").map(Number));
}
// s초 뒤의 시험관의 상태
queue = new Queue();

// [바이러스 번호, 열 위치, 행 위치] 넣을 배열 (정렬 위한 임시 배열)
let temp = [];
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (graph[i][j] != 0) {
      temp.push([graph[i][j], i, j])
    }
  }
}

// 바이러스 번호 순대로 정렬
temp.sort((a, b) => a[0] - b[0]);
// 큐에 삽입
for (let t of temp) queue.enqueue(t)

// s번 반복
while (s>0) {
  let queueLen = queue.getLength();

  // 1번 반복
  for (let i=0; i<queueLen; i++) {
    let node = queue.dequeue();
    let [virus, posX, posY] = node;
  
    // 상하좌우 이동
    for (let move of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
      let next = [posX + move[0], posY + move[1]];
      if (next[0] >= 0 && next[1] >= 0 && next[0] <= n - 1 && next[1] <= n - 1) {
        if (graph[next[0]][next[1]] == 0) {
          graph[next[0]][next[1]] = virus;
          queue.enqueue([virus, ...next]);
        }
      }
    }
  }
  s--;
}

console.log(graph[x-1][y-1]);