백준 - 14940 쉬운 최단거리 (BFS) JS

해당 문제 풀이는 구글에 자바스크립트 풀이 방법이 존재하지 않길래 포스팅하게 되었다.

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

 

 

 

풀이 방식은 다음과 같다.

1. 먼저 "2"로 표현된 목표 지점을 찾는다. 

그리고 이를 찾는 과정에서 "원래갈 수 있는 땅인 부분 중 도달할 수 없는 위치"는 "-1"로 표현되어야 하므로, 전체적인 배열 matrix에서 "1"로 표현되어 있는 값을 미리 모두 -1로 수정한다. (findStarting 함수)

2. BFS 함수를 구현한다.

로직은 [이동거리, 위치] 를 요소로 갖는 queue를 사용하여 구현했고, visited 배열을 통해 이미 방문한 곳은 다시 방문하지 않도록 했다. 이때, 상하좌우로 이동하였을 때 이동이 가능한지를 확인하여("0"이 아니거나, verify 함수가 true를 반환하는 경우), [이동거리 +1, 다음 위치] 를 queue에 추가하였다.

 

** 주의점

타 백준 문제와 다르게, 예제 입력에 첫줄로 등장하는 n, m은 각각 세로길이, 가로길이다. 이걸 처음에 반대로 해서 채점과정 90%에서 런타임 오류가 났다.

풀이과정 1과 같이 도달할 수 없는 위치는 미리 기본값을 -1로 설정해두는 것이 좋은데, 그렇지 않을 경우 마지막에 데이터를 가공하는 과정이 번거롭다. 

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split("\n")

const [N,M] = input.shift().split(" ").map(Number)

// 갈 수 있는 위치인지 검증하는 함수
const verify = (x,y) => {
  return x >= 0 && y >= 0 && x <= M-1 && y <= N-1
}

// BFS 함수
const BFS = (matrix,start) => {
  let visited = Array.from({length : N}, ()=> {
    return Array.from({length : M}, ()=> false)
  })

  let queue = [[0,start]]
  
  while (queue.length) {
    const [count, [x,y]] = queue.shift()
    if(visited[y][x]) continue
    else {
      visited[y][x] = true
      matrix[y][x] = count
      const direct = [[1,0],[0,1],[-1,0],[0,-1]]
      for(let i = 0 ; i < direct.length ; i++) {
        const [dx,dy] = direct[i]
        const [nextX, nextY] = [dx + x, dy + y]
        if(!verify(nextX,nextY)) continue
        else if(matrix[nextY][nextX] !== 0) {
          queue.push([count+1, [nextX, nextY]])
        }
      }
    }
  }
  return matrix
}

// "1"인 값을 "도달할 수 없는 위치"인 "-1"을 기본값으로 설정하며,
// 시작 위치인 "2"를 찾거든 위치값으로 반환하는 함수
const findStarting = (matrix) => {
  let startingNode
  for(let i = 0 ; i < N ; i++) {
    for(let j = 0 ; j < M ; j++) {
      if(matrix[i][j] === 1) matrix[i][j] = -1
      if(matrix[i][j] === 2) startingNode = [j,i]
    }
  }
  return startingNode
}

function solution(data) {
  let matrix = data.map(el=>el.split(" ").map(Number))
  const startingNode = findStarting(matrix)
  const result = BFS(matrix, startingNode)
  console.log(result.map((el)=>el.join(" ")).join("\n"))
}

solution(input)