백준 / 그래프 / 14940번 / 쉬운 최단거리 / JS

문제 간단설명

지도가 주어지면, 각 칸에서 목표지점까지의 거리를 출력하는 문제이다.

오직 가로와 세로로만 움직여 갈 수 있다.

 

제한 사항

• 2 <= n <= 1000
• 2 <= m <= 1000
• 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다.
• 입력에서 2는 단 한개이다.

 

실패 코드 (시간초과)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

const [n, m] = input.shift().split(' ').map(Number);
const map = input.map((row) => row.split(' ').map(Number));

const IMPOSSIBLE = 0;
const POSSIBLE = 1;
const GOAL = 2;

const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];

function solution() {
  const resultMap = Array.from({ length: n }, () => new Array(m));

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (map[i][j] === IMPOSSIBLE || map[i][j] === GOAL) {
        resultMap[i][j] = 0;
        continue;
      }

      resultMap[i][j] = bfs(i, j);
    }
  }

  printResultMap(resultMap);
}

function bfs(startRow, startCol) {
  const queue = [[startRow, startCol, 0]];
  const visited = Array.from({ length: n }, () => new Array(m).fill(false));

  visited[startRow][startCol] = true;

  while (queue.length > 0) {
    const [curRow, curCol, curCount] = queue.shift();

    if (map[curRow][curCol] === GOAL) {
      return curCount;
    }

    for (let d = 0; d < 4; d++) {
      const nr = curRow + dr[d];
      const nc = curCol + dc[d];

      if (!isValid(nr, nc)) {
        continue;
      }
      if (visited[nr][nc]) {
        continue;
      }
      if (map[nr][nc] === IMPOSSIBLE) {
        continue;
      }

      visited[nr][nc] = true;
      queue.push([nr, nc, curCount + 1]);
    }
  }
}

function isValid(row, col) {
  return 0 <= row && row < n && 0 <= col && col < m;
}

function printResultMap(resultMap) {
  console.log(resultMap.map((row) => row.join(' ')).join('\n'));
}

solution();

 

먼저 그냥 문제 그대로 구현해보았다.

각 칸에서 목표지점까지 bfs로 얼마나 걸리는지 판단하게 했더니 시간초과가 났다.

최대 1000 * 1000의 배열이기 때문에 시간초과가 걸리는 것은 당연한 풀이이다...

 

성공 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

const [n, m] = input.shift().split(' ').map(Number);
const map = input.map((row) => row.split(' ').map(Number));

const IMPOSSIBLE = 0;
const POSSIBLE = 1;
const GOAL = 2;

const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];

const resultMap = Array.from({ length: n }, () => new Array(m).fill(-1));

function solution() {
  let [startRow, startCol] = getStartPosition();

  checkImpossible();
  bfs(startRow, startCol);
  printResultMap();
}

function getStartPosition() {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (map[i][j] === GOAL) {
        resultMap[i][j] = 0;
        return [i, j];
      }
    }
  }
}

function checkImpossible() {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (map[i][j] === IMPOSSIBLE) {
        resultMap[i][j] = 0;
      }
    }
  }
}

function bfs(startRow, startCol) {
  const queue = [[startRow, startCol, 0]];
  const visited = Array.from({ length: n }, () => new Array(m).fill(false));

  visited[startRow][startCol] = true;

  while (queue.length > 0) {
    const [curRow, curCol, curCount] = queue.shift();

    for (let d = 0; d < 4; d++) {
      const nr = curRow + dr[d];
      const nc = curCol + dc[d];

      if (!isValid(nr, nc)) {
        continue;
      }
      if (visited[nr][nc]) {
        continue;
      }
      if (map[nr][nc] === IMPOSSIBLE || map[nr][nc] === GOAL) {
        continue;
      }

      visited[nr][nc] = true;
      queue.push([nr, nc, curCount + 1]);
      resultMap[nr][nc] = curCount + 1;
    }
  }
}

function isValid(row, col) {
  return 0 <= row && row < n && 0 <= col && col < m;
}

function printResultMap() {
  console.log(resultMap.map((row) => row.join(' ')).join('\n'));
}

solution();

 

반대로 생각해서 각 칸에서 목표지점까지 가는 것을 생각하지 말고, 목표지점에서 각 칸까지 얼마나 걸리는지 구한다고 생각해보자.

그렇다면 시작지점을 목표지점으로 잡고, 가로와 세로로 퍼져나가면서 각 칸에 대해서 이동거리를 표시해주면 한번의 bfs로 문제를 해결할 수 있다.