글 읽기 - [node.js] 시간초과

qorgkr26 2년 전 0

계속 시간 초과 아니면 메모리 초과가 나네요 지나가시는 고수님들의 도움 부탁드립니다..!!

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

const [n, m] = input[0].split(' ').map((x) => +x);

let map = Array.from(Array(n), () => new Array());

for (let i = 1; i <= n; i++) {
  map[i - 1] = input[i].split('').map((x) => +x);
}

const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];

let visited = Array.from(Array(n), () => new Array(m).fill(-1)); 
let dist = Array.from(Array(n), () => new Array(m).fill(Infinity));
visited[0][0] = 0;
dist[0][0] = 1;

const bfs = (start) => {
  let queue = [start];
  while (queue.length) {
    let [row, col] = queue.shift();
    if (row === n - 1 && col === m - 1) {
      break;
    }
    for (let i = 0; i < dx.length; i++) {
      if (
        row + dx[i] < 0 ||
        row + dx[i] >= n ||
        col + dy[i] < 0 ||
        col + dy[i] >= m
      )
        continue;

      if (map[row + dx[i]][col + dy[i]] === 1 && visited[row][col] === 1)
        continue;
      if (visited[row][col] === 1 && visited[row + dx[i]][col + dy[i]] === 0)
        continue;

      if (dist[row + dx[i]][col + dy[i]] < dist[row][col] + 1) continue;

      visited[row][col] === 1
        ? (visited[row + dx[i]][col + dy[i]] = 1)
        : (visited[row + dx[i]][col + dy[i]] = 0);

      if (visited[row][col] === 0) {
        map[row + dx[i]][col + dy[i]] === 1
          ? (visited[row + dx[i]][col + dy[i]] = 1)
          : (visited[row + dx[i]][col + dy[i]] = 0);
      }

      dist[row + dx[i]][col + dy[i]] = dist[row][col] + 1;
      queue.push([row + dx[i], col + dy[i]]);
    }
  }
};

bfs([0, 0]);

if (dist[n - 1][m - 1] === Infinity) console.log(-1);
else console.log(dist[n - 1][m - 1]);

nahwasa 2년 전 1

아마 무한루프로 빠지는 구간이 있을것으로 보이네요.

일단 그 부분까진 확인을 안해봤는데,

https://www.acmicpc.net/board/...

애초에 이 글에 제가 답글 달아둔 케이스를 통과 못하기 때문입니다

저 질문글 한번 확인해보셔요!

qorgkr26 2년 전 0

감사합니다! 덕분에 통과했습니다.

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

문제

문제

출처

ICPC

[node.js] 시간초과

qorgkr26 2년 전 0

nahwasa 2년 전 1

qorgkr26 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말