글 읽기 - node.js 메모리 초과, 시간 초과

greenish0902 2년 전 0

틀린 부분을 도무자 모르겠습니다 ... ㅠㅠ

bfs 로 구현했고, 장애물의 번호마다 위치 확인했습니다.

* 배열 shift, push 메서드를 사용하면 시간 초과가 발생하고

* class Queue 를 직접 구현해 사용하면 메모리 초과가 발생합니다... ㅠㅠ

bfs continue 조건도 모두 잘 넣은 것 같은데 메모리 초과 / 시간 초과가 계속 발생하네요..

놓친 반례가 있을까요?

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

class Node {
  constructor(data) {
    this.value = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  enqueue(val) {
    let node = new Node(val);
    if (!this.first) {
      this.first = node;
      this.last = node;
    } else {
      this.last.next = node;
      this.last = node;
    }
    return ++this.size;
  }

  dequeue() {
    if (!this.first) return null;
    let node = this.first;
    if (this.first == this.last) this.last = null;
    this.first = this.first.next;
    this.size--;
    return node.value;
  }

  length() {
    return this.size;
  }
}

let lineNum = 0;
const input = () => stdin[lineNum++];
const dir = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  let count = 0;
  // get Input
  const [N, M] = input().split(" ").map(Number);
  let visited = [];
  let arr = [];
  let queue = new Queue();
  let elem;
  for (let row = 0; row < N; row++) {
    visited[row] = [];
    for (let col = 0; col < M; col++) visited[row][col] = new Array(5).fill(0);
    elem = input().split(" ").map(Number);
    arr.push(elem);
    if (elem.includes(9)) initQueue(row, elem);
  }

  // solution: bfs
  bfs();
  console.log(count);
  process.exit();

  // solution functions
  // main: bfs
  function bfs() {
    let spaceNum, ndirIdx;
    while (queue.length() > 0) {
      let [row, col, currentDir] = queue.dequeue();
      row += dir[currentDir][0];
      col += dir[currentDir][1];
      if (row < 0 || row >= N || col < 0 || col >= M) continue;

      spaceNum = arr[row][col];
      if (spaceNum == 9) continue;

      ndirIdx = getNewDir(spaceNum, currentDir);
      if (visited[row][col][ndirIdx]) continue;
      visited[row][col][ndirIdx] = 1;

      if (visited[row][col][4]) {
        if (Math.abs(ndirIdx - currentDir) == 2) continue;
      } else {
        visited[row][col][4] = 1;
        count++;
      }

      queue.enqueue([row, col, ndirIdx]);
    }
  }

  // check stacknum & change direction
  function getNewDir(stackNum, currentDir) {
    switch (stackNum) {
      case 0: // no obstacle
        return currentDir;
      case 1: // col
        if (currentDir == 0 || currentDir == 2) return currentDir;
        return 4 - currentDir;
      case 2: // row
        if (currentDir == 1 || currentDir == 3) return currentDir;
        return 2 - currentDir;
      case 3: // side /
        if (currentDir == 0 || currentDir == 1) return 1 - currentDir;
        return 5 - currentDir;
      case 4: // side \
        return 3 - currentDir;
    }
  }

  // push starting points into init arr
  function initQueue(row, elem) {
    for (let col = 0; col < M; col++) {
      if (elem[col] == 9) {
        visited[row][col][4] = 1;
        count++;
        for (let dirIdx = 0; dirIdx < 4; dirIdx++) {
          queue.enqueue([row, col, dirIdx]);
          visited[row][col][dirIdx] = 1;
        }
      }
    }
  }
});

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

node.js 메모리 초과, 시간 초과

greenish0902 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말