[백준] 16197번 두 동전 Javascript(Node Js)

문제 링크

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

알고리즘: BFS, 백트래킹

문제 요약

NxM 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다. 버튼은 "왼", "오", "위", "아래"와 같이 4가지가 있고 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

=> 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
=> 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
=> 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. 이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

풀이 요약

먼저 두 동전의 위치를 Queue에 넣는다. 그리고 각각 버튼을 눌렀을 때 두 동전의 새로운 위칫값을 구한다. nx1 ny1, nx2 ny2 => 일단 이 좌표가 벽인지 확인할 필요가 있는데 벽이면 원래 x, y 값을 넣어준다. 이 동전들이 이미 방문했던 좌표라면 pass 해주고 그렇지 않으면 push 조건에 만족하는지 체크해준다. Queue에 push 조건은 두 동전이 모두 보드에서 떨어지면 안 되며, 두 동전이 같은 위치에 있지 않아야 한다. 이 모든 조건을 만족했다면 Queue에 push하고 Queue에서 pop_left 할 때 두 개 동전 중 하나만 보드에 있다면, return 해주고 cut 값을 출력해주면 끝이다.

소스코드

class Queue {
    constructor() {
        this.storage = {};
        this.front = 0;
        this.rear = -1;
    }

    size() {
        if (this.front > this.rear) {
            return 0;
        } else {
            return this.rear - this.front + 1;
        }
    }

    push(value) {
        this.rear += 1;
        this.storage[this.rear] = value;
    }

    pop_left() {
        let value = this.storage[this.front];
        if (this.size()) {
            delete this.storage[this.front];
            this.front += 1;
        }
        return value;
    }
}
const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [N, M] = inputData[0].trim().split(' ').map(x => x * 1);
let board = Array.from(Array(N), () => Array(M));
let visited_map = new Map(); //방문 체크를 위한 Map
let coin = [];
for (let i = 1; i < inputData.length; i++) {
    let input = inputData[i].trim().split('');
    for (let j = 0; j < input.length; j++) {
        if (input[j] === 'o') {
            board[i - 1][j] = '.';
            coin.push([j, i - 1]);
        } else {
            board[i - 1][j] = input[j]
        }
    }
}

if(N===1 && M===1) {
    console.log(-1);
} else {
    console.log(BFS());
}

function BFS() {
    let que = new Queue();
    let [cx1, cy1] = coin[0];
    let [cx2, cy2] = coin[1];
    visited_map.set(`${cx1}${cy1}${cx2}${cy2}`, true);
    que.push({ c1: [cx1, cy1], c2: [cx2, cy2], cut: 0 });
    let wx = [-1, 1, 0, 0]; //왼쪽 오른쪽 위 아래
    let wy = [0, 0, -1, 1]; //왼쪽 오른쪽 위 아래
    while (que.size() !== 0) {
        let value = que.pop_left();
        let [x1, y1] = value.c1; //첫번째 동전에 위치
        let [x2, y2] = value.c2; //두번째 둥전에 위치
        if (((x1 >= 0 && x1 <= M - 1) && (y1 >= 0 && y1 <= N - 1)) && (x2 < 0 || x2 >= M) || (y2 < 0 || y2 >= N)) return value.cut;
        if (((x2 >= 0 && x2 <= M - 1) && (y2 >= 0 && y2 <= N - 1)) && (x1 < 0 || x1 >= M) || (y1 < 0 || y1 >= N)) return value.cut;
        if (value.cut < 10) {
            for (let i = 0; i < 4; i++) {
                let nx1 = x1 + wx[i];
                let ny1 = y1 + wy[i];
                let nx2 = x2 + wx[i];
                let ny2 = y2 + wy[i];
                if (((nx1 >= 0 && nx1 <= M - 1) && (ny1 >= 0 && ny1 <= N - 1))) {
                    if (board[ny1][nx1] === '#') {
                        nx1 = x1;
                        ny1 = y1;
                    }
                }
                if (((nx2 >= 0 && nx2 <= M - 1) && (ny2 >= 0 && ny2 <= N - 1))) {
                    if (board[ny2][nx2] === '#') {
                        nx2 = x2;
                        ny2 = y2;
                    }
                }
                let vn = `${nx1}${ny1}${nx2}${ny2}`; //visited number
                if (visited_map.get(vn) === undefined) {
                    if (!(((nx1 < 0 || nx1 >= M) || (ny1 < 0 || ny1 >= N)) && ((nx2 < 0 || nx2 >= M) || (ny2 < 0 || ny2 >= N)))) {
                        if (!((nx1 === nx2) && (ny1 === ny2))) {
                            visited_map.set(vn, true);
                            que.push({ c1: [nx1, ny1], c2: [nx2, ny2], cut: value.cut + 1 });
                        }
                    }
                }
            }
        }
    }
    return -1;
}