[카카오 인턴] 경주로 건설

CCKN·2020년 12월 25일

js 다익스트라 알고리즘 프로그래머스

코딩테스트

목록 보기

12/24

[카카오 인턴] 경주로 건설

문제 링크

문제 요약

목적지까지 가는 최소한의 비용 계산
다익스트라 알고리즘 예상

목적지로 가는 형태에 2가지가 있음에 주의할 것

제한사항

[제한사항]
board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
board 배열의 각 원소의 값은 0 또는 1 입니다.
도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

Input

도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board

output

경주로를 건설하는데 필요한 최소 비용

해결방법

다익스트라 알고리즘으로 생각해보자
각 좌표에 도착하는 방법은 두가지가 있다.
1. isVertical

다익스트라 알고리즘은 ?
각 좌표에 대한 코스트를 저장해두고 가까운 곳부터 큐로 담는다.
큐를 순회하고 다음 목적지에 드는 비용을 저장해둔다.

최초

const DIRECTION = [
  { dir: 'U', dx: 0, dy: -1, type: 'Vertical' },
  { dir: 'D', dx: 0, dy: 1, type: 'Vertical' },
  { dir: 'L', dx: -1, dy: 0, type: 'Horizontal' },
  { dir: 'R', dx: 1, dy: 0, type: 'Horizontal' },
]
function solution(board) {
  const n = board.length
  let dijkArr = {
    Horizontal: Array.from(Array(n), () => Array(n).fill(Infinity)),
    Vertical: Array.from(Array(n), () => Array(n).fill(Infinity)),
  }
  const isMovable = (x, y) => {
    if (0 > x || x >= n || 0 > y || y >= n) {
      return false
    }
    if (board[x][y] === 1) {
      return false
    }
    return true
  }
  const dijkQueue = []
  dijkQueue.push({ position: { x: 0, y: 0 }, type: 'Horizontal', cost: 0 })
  dijkQueue.push({ position: { x: 0, y: 0 }, type: 'Vertical', cost: 0 })
  dijkArr.Horizontal[0][0] = 0
  dijkArr.Vertical[0][0] = 0
  const results = []
  // for (let i = 0; i < 10; i++) {
  while (dijkQueue.length) {
    const current = dijkQueue.shift()
    //print(dijkArr, dijkQueue)
    DIRECTION.forEach((d) => {
      const tX = current.position.x + d.dx
      const tY = current.position.y + d.dy
      if (!isMovable(tX, tY)) {
        return
      }
      let newCost = current.cost
      if (d.dir === 'U' || d.dir === 'D') {
        if (current.type === 'Vertical') {
          newCost += 100
        } else {
          newCost += 600
        }
      } else {
        if (current.type === 'Vertical') {
          newCost += 600
        } else {
          newCost += 100
        }
      }
      const savedData = dijkArr[d.type][tX][tY]
      if (savedData > newCost) {
        const dist = {
          position: {
            x: current.position.x + d.dx,
            y: current.position.y + d.dy,
          },
          cost: newCost,
          type: d.type,
        }
        dijkQueue.push(dist)
        dijkArr[d.type][tX][tY] = newCost
        if (current.position.x === n - 1 && current.position.y === n - 1) {
          results.push(current.cost)
        }
      }
    })
  }
  return Math.min(
    dijkArr.Horizontal[n - 1][n - 1],
    dijkArr.Vertical[n - 1][n - 1]
  )
}

통과

처음써보는 다익스트라 알고리즘이라 소스코드가 많이 지저분하다.

리팩토링을 수행하자

리팩토링

const DIRECTION = [
  { dx: 0, dy: -1, type: 'Vertical' },
  { dx: 0, dy: 1, type: 'Vertical' },
  { dx: -1, dy: 0, type: 'Horizontal' },
  { dx: 1, dy: 0, type: 'Horizontal' },
]

function solution(board) {
  const n = board.length
  let dijkArr = {
    Horizontal: Array.from(Array(n), () => Array(n).fill(Infinity)),
    Vertical: Array.from(Array(n), () => Array(n).fill(Infinity)),
  }
  const isMovable = (x, y) => {
    if (0 > x || x >= n || 0 > y || y >= n) return false
    if (board[x][y] === 1) return false
    return true
  }

  const dijkQueue = []
  dijkQueue.push({ position: { x: 0, y: 0 }, type: 'Horizontal', cost: 0 })
  dijkQueue.push({ position: { x: 0, y: 0 }, type: 'Vertical', cost: 0 })
  dijkArr.Horizontal[0][0] = 0
  dijkArr.Vertical[0][0] = 0

  while (dijkQueue.length) {
    const current = dijkQueue.shift()
    DIRECTION.forEach((d) => {
      const x = current.position.x + d.dx
      const y = current.position.y + d.dy
      if (!isMovable(x, y)) return
      const cost = current.cost + (d.type === current.type ? 100 : 600)
      const type = d.type
      const savedData = dijkArr[d.type][x][y]
      if (savedData > cost) {
        const dist = {
          position: { x, y },
          cost,
          type,
        }
        dijkQueue.push(dist)
        dijkArr[type][x][y] = cost
      }
    })
  }

  return Math.min(
    dijkArr.Horizontal[n - 1][n - 1],
    dijkArr.Vertical[n - 1][n - 1]
  )
}