16197 두 동전

문제

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

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

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

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

입력

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

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

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

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

출력

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

====

문제 분석

동전 2개를 상하좌우로 동시에 움직이면서 둘 중 하나가 먼저 영역 바깥으로 나간다면 이동 횟수를 출력하는 문제이다.

(참고로 10번 이상 버튼 클릭하면 -1을 출력해야 한다는 지문이 있다)

동전이 정답이 되는 경우는 하나는 영역 바깥으로 나가면서 다른 하나는 나가지 않는 경우이다.

이것을 위해 체크하는 함수인 isOut을 만들어준다.

const isOut = (x, y, n, m) => {
    if (x < 0 || y < 0 || x >= n || y >= m) return true;
    return false;
};

이 함수를 이용하여 현재 위치에서 다음 위치를 isOut을 통해 바깥으로 나가는지 체크한 후 둘 중 하나가 아웃이라면 정답을 출력한다.

const [nfx, nfy] = [fx + dx[i], fy + dy[i]];
const [nsx, nsy] = [sx + dx[i], sy + dy[i]];

const isFirstOut = isOut(nfx, nfy, n, m);
const isSecondOut = isOut(nsx, nsy, n, m);
if (isFirstOut && isSecondOut) continue;
if (isFirstOut && !isSecondOut) {
    console.log(cnt + 1);
    process.exit(0);
}
if (isSecondOut && !isFirstOut) {
    console.log(cnt + 1);
    process.exit(0);
}

이제 정답이 아니지만 동전이 이동할 수 있는 경우는 

1) 동시에 방문해본 적 없는 위치

2) 하나는 벽에 부딪혔지만 다른 하나는 이동이 가능한 경우다

1)번의 동시에 방문해본적 없는 경우는 [a,b,c,d] 으로 이루어진 4차원 배열을 만들어서 중복 체크를 해보거나 set으로 문장을 만들어서 체크하는 방법이 있다.

나는 후자로 체크해봄

const visited = new Set();

const isPossible = (a, b, c, d, s) => {
    const str = `${a}${b}${c}${d}`;
    if (s.has(str)) return false;
    s.add(str);
    return true;
};

isPossible 함수에는 좌표들과 visited를 넣어서 중복 체크해본다.

벽에 부딪히는지 체크하는 함수를 만든 후 둘다 벽에 부딪히면 패스하고 하나만 부딪힌다면 이동을 한다.

const isWall = (x, y, gr) => {
    if (gr[x][y] === '#') return true;
    return false;
};

아래는 하나만 벽에 부딪혀서 이동가능한 경우와 둘다 벽에 부딪혀서 이동 못하는 경우

const isFirstWall = isWall(nfx, nfy, gr);
const isSecondWall = isWall(nsx, nsy, gr);
if (isFirstWall && isSecondWall) continue;
if (isFirstWall && !isSecondWall) {
    if (isPossible(fx, fy, nsx, nsy, visited)) {
        q.push([[fx, fy], [nsx, nsy], cnt + 1]);
    }
    continue;
}
if (isSecondWall && !isFirstWall) {
    if (isPossible(nfx, nfy, sx, sy, visited)) {
        q.push([[nfx, nfy], [sx, sy], cnt + 1]);
    }
    continue;
}

아래는 둘다 방문해본 적 없으면서 이동 가능한 경우다.

if (isPossible(nfx, nfy, nsx, nsy, visited)) {
    q.push([[nfx, nfy], [nsx, nsy], cnt + 1]);
}

정답 코드

const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];

const isOut = (x, y, n, m) => {
    if (x < 0 || y < 0 || x >= n || y >= m) return true;
    return false;
};

const isWall = (x, y, gr) => {
    if (gr[x][y] === '#') return true;
    return false;
};

const isPossible = (a, b, c, d, s) => {
    const str = `${a}${b}${c}${d}`;
    if (s.has(str)) return false;
    s.add(str);
    return true;
};

const main = (n, m, gr) => {
    const q = [];
    const one = [-1, -1];
    const two = [-1, -1];
    const visited = new Set();

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] === 'o') {
                if (one[0] === -1) {
                    one[0] = i;
                    one[1] = j;
                } else {
                    two[0] = i;
                    two[1] = j;
                    break;
                }
            }
        }
    }
    visited.add(`${one[0]}${one[1]}${two[0]}${two[1]}`);
    q.push([one, two, 0]);
    while (q.length) {
        const [[fx, fy], [sx, sy], cnt] = q.shift();
        if (cnt >= 10) {
            continue;
        }
        for (let i = 0; i < 4; i++) {
            const [nfx, nfy] = [fx + dx[i], fy + dy[i]];
            const [nsx, nsy] = [sx + dx[i], sy + dy[i]];

            const isFirstOut = isOut(nfx, nfy, n, m);
            const isSecondOut = isOut(nsx, nsy, n, m);
            if (isFirstOut && isSecondOut) continue;
            if (isFirstOut && !isSecondOut) {
                console.log(cnt + 1);
                process.exit(0);
            }
            if (isSecondOut && !isFirstOut) {
                console.log(cnt + 1);
                process.exit(0);
            }
            const isFirstWall = isWall(nfx, nfy, gr);
            const isSecondWall = isWall(nsx, nsy, gr);
            if (isFirstWall && isSecondWall) continue;
            if (isFirstWall && !isSecondWall) {
                if (isPossible(fx, fy, nsx, nsy, visited)) {
                    q.push([[fx, fy], [nsx, nsy], cnt + 1]);
                }
                continue;
            }
            if (isSecondWall && !isFirstWall) {
                if (isPossible(nfx, nfy, sx, sy, visited)) {
                    q.push([[nfx, nfy], [sx, sy], cnt + 1]);
                }
                continue;
            }
            if (isPossible(nfx, nfy, nsx, nsy, visited)) {
                q.push([[nfx, nfy], [nsx, nsy], cnt + 1]);
            }
        }
    }

    console.log(-1);
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ');
const gr = input.slice(1).map((str) => str.split(''));
main(n, m, gr);