[node.js, 백준]16197 - 두 동전

 

목차

 문제

링크

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

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

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

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

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

 

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

 

주저리

dfs와 bfs풀이가있지만 bfs가 문제 활용도가 높아서 bfs로 해결하려하였다..

하지만 처음 작성한시간을 너무 허비해서 코드 최적화가 안되어서 결국 구글링을 하여서 나만의 방법으로 다시 풀려고 하였다.

처음에 착각한게있었는데 이게 동전이 두개라서 각 하나의 동전을 check하는 방식으로 BFS를 해가면 나중에 값이 덮어씌어져서 답을 제대로 찾을 수 가없다.

그래서 4중 배열로 두동전의 위치를 다 가져서 유니크하게 가게 하려고 하였다.

그렇게해서 bfs로 두동전을 검사해 둘중 하나만 떨어지면 정답을 찾아서 루프를 나와주고 벽이있다면 그 동전은 그대로 있게 하는식으로 bfs를 수행해주면된다.

 

풀이

 입력 파싱

입력을 파싱하여 미로와 동전의 위치를 읽어온다.

let input = `5 3
###
.o.
###
.o.
###`

let real = input.trim().split("\n");
let [first, ...rests] = real;
let maze = rests.map(v => [...v]);
let [N, M] = first.split(" ").map(Number);

 

 거리 배열 초기화

두 동전의 위치에 대한 거리 배열을 초기화한다.

let distanceArrays = Array.from({ length: N }, () => Array.from({ length: M }, () => Array.from({ length: N }, () => Array.from({ length: M }).fill(-1))));

 

 방향 벡터 정의

네 방향(상, 하, 좌, 우)으로 이동할 수 있도록 방향 벡터 정의.

let dx = [-1, 1, 0, 0]
let dy = [0, 0, 1, -1]

 

 체크 함수 정의

현재 상태에서 동전을 이동시키고, 두 동전 중 하나가 떨어지면 결과를 반환

function check(coin1, coin2, count) {
    let newCoins = [];
    for (let i = 0; i < dx.length; i++) {
        let newCoin1 = { x: coin1.x + dx[i], y: coin1.y + dy[i] };
        let newCoin2 = { x: coin2.x + dx[i], y: coin2.y + dy[i] };
        let stateA = false;
        let stateB = false;
        if (newCoin1.x >= 0 && newCoin1.x < M && newCoin1.y >= 0 && newCoin1.y < N) stateA = true;
        if (newCoin2.x >= 0 && newCoin2.x < M && newCoin2.y >= 0 && newCoin2.y < N) stateB = true;
        if (stateA ^ stateB) {
            mins = Math.min(count, mins);
            return false;
        } else if (stateA && stateB) {
            if (maze[newCoin1.y][newCoin1.x] === '#') {
                newCoin1 = coin1;
            }
            if (maze[newCoin2.y][newCoin2.x] === '#') {
                newCoin2 = coin2;
            }
            if (distanceArrays[newCoin1.y][newCoin1.x][newCoin2.y][newCoin2.x] === -1) {
                distanceArrays[newCoin1.y][newCoin1.x][newCoin2.y][newCoin2.x] = count;
                newCoins.push([newCoin1, newCoin2]);
            }
        }
    }
    return newCoins;
}

 

 동전 위치 가져오기

미로에서 동전 위치를 가져온다.

function getCoinCoord(maze) {
    let coins = [];
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (maze[i][j] === 'o') {
                coins.push({ x: j, y: i });
            }
        }
    }
    return coins;
}

 

 해결 함수 정의

BFS(너비 우선 탐색)를 사용하여 두 동전의 상태를 큐에 넣고, 최소 이동 횟수를 찾는다.

function solution() {
    let que = [];
    let coins = getCoinCoord(maze);
    que.push(coins);
    distanceArrays[coins[0].y][coins[0].x][coins[1].y][coins[1].x] = 0;
    while (que.length !== 0) {
        let [coin1, coin2] = que.shift();
        let count = distanceArrays[coin1.y][coin1.x][coin2.y][coin2.x];
        if (count >= 10) {
            mins = -1;
            break;
        }
        let newCoins = check(coin1, coin2, count + 1);
        if (!newCoins) {
            break;
        }
        que.push(...newCoins);
        if (que.length === 0) {
            mins = -1;
            break;
        }
    }
    console.log(mins);
}

 

 해결 함수 실행

해결 함수를 실행하여 결과를 출력

solution();

 

 코드

// 두 동전
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();

// o: 동전
// .: 빈칸
// #: 벽

let real = input.trim().split("\n");
let [first, ...rests] = real;
let maze = rests.map(v => [...v]);
let [N, M] = first.split(" ").map(Number);
let distanceArrays = Array.from({ length: N }, () => Array.from({ length: M }, () => Array.from({ length: N }, () => Array.from({ length: M }).fill(-1))));
let mins = Infinity;
let dx = [-1, 1, 0, 0]
let dy = [0, 0, 1, -1]
function check(coin1, coin2, count) {
    let newCoins = [];
    for (let i = 0; i < dx.length; i++) {
        let newCoin1 = { x: coin1.x + dx[i], y: coin1.y + dy[i] };
        let newCoin2 = { x: coin2.x + dx[i], y: coin2.y + dy[i] };
        let stateA = false;
        let stateB = false;
        // 좌표안에있다면
        if (newCoin1.x >= 0 && newCoin1.x < M && newCoin1.y >= 0 && newCoin1.y < N) stateA = true;
        if (newCoin2.x >= 0 && newCoin2.x < M && newCoin2.y >= 0 && newCoin2.y < N) stateB = true;
        // 둘중하나만 true
        if (stateA ^ stateB) {
            mins = Math.min(count, mins);
            return false;
        }
        // 둘다 true
        else if (stateA && stateB) {
            if (maze[newCoin1.y][newCoin1.x] === '#') {
                newCoin1 = coin1;
            }
            if (maze[newCoin2.y][newCoin2.x] === '#') {
                newCoin2 = coin2;
            }
            if (distanceArrays[newCoin1.y][newCoin1.x][newCoin2.y][newCoin2.x] === -1) {
                distanceArrays[newCoin1.y][newCoin1.x][newCoin2.y][newCoin2.x] = count;
                // console.log({ newCoin1, newCoin2 })
                newCoins.push([newCoin1, newCoin2]);
            }

        }
    }
    return newCoins
}

function getCoinCoord(maze) {
    let coins = [];
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (maze[i][j] === 'o') {
                coins.push({ x: j, y: i });
            }
        }
    }
    return coins;
}

// 두 동전중 하나만 떨어뜨려야함
// 10번이상누르게되면 -1
function solution() {
    let que = [];
    let coins = getCoinCoord(maze);
    que.push(coins);
    distanceArrays[coins[0].y][coins[0].x][coins[1].y][coins[1].x] = 0;
    // console.log(maze, coins, distanceArrays);
    while (que.length !== 0) {
        let [coin1, coin2] = que.shift();

        let count = distanceArrays[coin1.y][coin1.x][coin2.y][coin2.x];
        if (count >= 10) {
            // console.log("옴?")
            mins = -1;
            break;
        }
        let newCoins = check(coin1, coin2, count + 1);
        // console.log(coin1, coin2, count, newCoins)
        if (!newCoins) {
            break;
        }
        que.push(...newCoins);

        if (que.length === 0) {
            mins = -1;
            break;
        }
    }
    console.log(mins);
}
solution();