[백준BOJ] 1584번 게임.js

 

백준 저지에서 게임을 자바스크립트를 통해 풀어 보았다. 

 

1584번 게임.js

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

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

1584번: 게임

1584번 게임

문제

세준이는 위험한 지역에서 탈출하는 게임을 하고 있다. 이 게임에는 세준이가 들어갈 수 없는 죽음의 구역이 있고, 들어가서 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역이 있다. 그리고, 자유롭게 생명의 위협없이 움직일 수 있는 안전한 구역이 있다. (안전한 구역은 죽음의 구역과 위험한 구역을 제외한 나머지 이다.)
세준이는 (0, 0)에서 출발해서 (500, 500)으로 가야 한다. 세준이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있다. 현재 세준이는 (0, 0)에 있다. 그리고, 게임 판을 벗어날 수는 없다.
세준이가 (0, 0)에서 (500, 500)으로 갈 때 잃는 생명의 최솟값을 구하는 프로그램을 작성하시오.

설명

BFS를 통해 풀 수 있다.

 

isIn함수를 만들어서 위험구역, 죽음 구역, 전체 구역에 대해서 안에 있는지를 확인했다. 단 확인할 때마다 반복문을 계속 돌기 때문에 처음부터 배열로 만들었으면 더 효율적인 코드를 짤 수 있었을 것 같다.

 

전체 배열을 선언할 때는 생명 값으로 올 수 있는 최댓값인 25000보다 큰 25001로 초기화한다.

[0,0]은 구역에 상관없이 영향을 받지 않으므로 0으로 초기화한다.

 

BFS를 통해 배열을 방문한다. 배열에는 해당 위치까지, 현재까지 구한 생명의 최솟값을 저장한다. 

다음 구역이 위험구역이라면 현재 구역에 저장된 생명 값에 1을 더한 값을 저장하고, 안전구역이라면 현재 구역에 저장된 생명 값을 저장한다.

 

이때 죽음 구역이라면 아예 방문하지 않으며, 위험구역이나 안전구역일 경우 현재 구한 생명 값보다 클 경우 방문한다.

 

모든 BFS를 돌고 배열의 [500,500] 좌표가 정답이다.

만약 [500,500]좌표가 25001이라면 방문하지 못한 것이므로 -1을 출력한다.

 

코드

const input = require('fs').readFileSync('C:/Users/tomy9/Desktop/Moz1e git/Algorithm/BaekJoon/input.txt').toString().split("\n")

const N = Number(input[0])//위험
let index = 1
const danger = (() => {
    const result = []
    for (let i = 0; i < N; i++, index++) {
        result.push(input[index].split(" ").map(Number))
    }
    return result
})()

const M = Number(input[index++])//죽음
const death = (() => {
    const result = []
    for (let i = 0; i < M; i++, index++) {
        result.push(input[index].split(" ").map(Number))
    }
    return result
})()

const isIn = (x, y, area) => {
    const check = area.find((eachArea => {
        const [minX, minY, maxX, maxY] = [
            Math.min(eachArea[0], eachArea[2]),
            Math.min(eachArea[1], eachArea[3]),
            Math.max(eachArea[0], eachArea[2]),
            Math.max(eachArea[1], eachArea[3]),
        ]
        if (minX <= x && x <= maxX && minY <= y && y <= maxY) return true
        else return false
    }))
    if (check) return true
    else return false
}


const area = Array.from(Array(501), () => new Array(501).fill(25001))
area[0][0] = 0
const bfs = () => {
    const dx = [0, 0, 1, -1]
    const dy = [1, -1, 0, 0]

    const q = []
    q.push({ x: 0, y: 0 })
    while (q.length != 0) {
        const cur = q.shift()
        for (let i = 0; i < 4; i++) {
            const next = { x: cur.x + dx[i], y: cur.y + dy[i] }

            if (isIn(next.x, next.y, [[0, 0, 500, 500]])) {
                const nextPoint = (() => {
                    if (isIn(next.x, next.y, danger)) return area[cur.x][cur.y] + 1
                    else return area[cur.x][cur.y]
                })()
                if (!isIn(next.x, next.y, death)) {
                    if (area[next.x][next.y] > nextPoint) {
                        area[next.x][next.y] = nextPoint
                        q.push(next)
                    }
                }
            }
        }
    }
}

bfs()
if (area[500][500] == 25001) console.log(-1)
else console.log(area[500][500])