알고리즘 풀이 - 경주로 건설
January 09, 2021
[카카오 인턴] 경주로 건설
문제 요약
목적지까지 가는 최소한의 비용 계산 다익스트라 알고리즘 예상
목적지로 가는 형태에 2가지가 있음에 주의할 것
제한사항
[제한사항] board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다. board 배열의 각 원소의 값은 0 또는 1 입니다. 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다. 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다. board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다. 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.
Input
도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board
output
경주로를 건설하는데 필요한 최소 비용
해결방법
- 다익스트라 알고리즘으로 생각해보자
-
각 좌표에 도착하는 방법은 두가지가 있다.
- 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]
)
}
통과 - 소요 시간도 많이 줄었다.
추가 금액 구하는 부분 리팩토링
변수명 수정
필요 없는 부분 삭제
