구슬 탈출 2

문제

언어

  • JavaScript

순서도

  1. 직사각형 보드에서 빨간 구슬과 파란 구슬의 위치 찾기
  2. 각 구슬의 위치에서 상, 하, 좌, 우로 기울이며, 가능한 모든 경우 만들기
  3. 그 중에서 빨간 구슬만 구멍으로 빠지는 경우들을 추리고, 그 중에서 최소로 기울인 경우의 횟수 구하기

문제 풀이 step 1

  • 본 문제는 완전 탐색 문제로, 모든 경우의 수를 만들어보고 그 경우 중에서 최적의 값을 찾는 문제입니다.
  • 구슬 탈출은 직사각형 보드에서 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임입니다.
  • 보드의 세로 크기는 N, 가로 크기는 M, 편의상 1 x 1 크기의 칸으로 나누어져 있습니다.
  • 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있습니다.
  • 빨간 구슬과 파란 구슬의 크기는 보드에서 1 x 1 크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있습니다.
  • 게임의 목표는 빨간 구슬을 구멍을 통해 빼내는 것입니다. 이때, 파란 구슬이 구멍에 들어가면 안됩니다.
  • 구슬은 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 합니다.
  • 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울이기와 같는 4 가지 동작이 가능합니다.
  • 각각의 동작에서 공은 동시에 움직입니다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패입니다.
  • 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패입니다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없습니다.
  • 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지합니다.
  • 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지입니다.
  • 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 뺴낼 수 있는지 구하는 문제입니다.

문제 풀이 step 2

  • 우선 보드에서 빨간 구슬과 파란 구슬의 위치를 구합니다.
  • 각 구슬을 상, 하, 좌, 우로 기울이며 가능한 모든 경우를 만듭니다.
    • 기울일 때, 구슬은 동시에 움직이기 때문에 약간의 조건이 필요합니다.
      • 만약 좌로 기울일 때, 각 구슬의 좌표를 파악해서 왼쪽에 있는 구슬을 먼저 움직이고, 다른 구슬을 움직여야 합니다.
      • 마찬가지로 하로 기울일 때, 각 구슬의 좌표를 파악해서 아래에 있는 구슬을 먼저 움직이고, 다른 구슬을 움직여야 합니다.
    • 이렇게 기울일 수 있는 모든 경우를 다 만들어봅니다.
      • 이 때, depth 변수를 이용해서 각 경우의 기울인 횟수를 파악해서 횟수가 10 을 넘어가면 그 경우는 버립니다.
      • 그리고 매 경우마다 파란 구슬이 구멍에 빠지는지 파악해서 구멍에 빠지면 그 경우도 버립니다.
      • 그리고 빨간 구슬만 구멍에 빠지면, 그 경우의 depth 값들 중에서 최소값을 갱신합니다.
  • 모든 경우를 만들어보고, 구한 최소값을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 최대 10 번까지만 기울이기 때문에 MAX 는 11 로 설정
const MAX = 11;

let ans = MAX;

// 상, 하, 좌, 우
const dir = [
	[0, -1],
	[0, 1],
	[-1, 0],
	[1, 0],
];

// 한 개의 구슬을 움직이는 함수
const move = (arr, x, y, dx, dy, i) => {
	while (true) {
		const [nx, ny] = [x + dir[i][0], y + dir[i][1]];

		if (arr[nx][ny] === "O") {
			[x, y] = [nx, ny];
			break;
		}

		if (arr[nx][ny] === "#") break;
		if (nx === dx && ny === dy) break;

		[x, y] = [nx, ny];
	}

	return [x, y];
};

// 보드를 기울이는 함수
const tilt = (arr, rx, ry, bx, by, i) => {
	// 상, 하, 좌, 우에 따라서
	// 먼저 움직여야 하는 구슬을 찾아서 움직이기
	if (i === 0) {
		if (ry <= by) {
			[rx, ry] = move(arr, rx, ry, bx, by, i);
			[bx, by] = move(arr, bx, by, rx, ry, i);
		} else {
			[bx, by] = move(arr, bx, by, rx, ry, i);
			[rx, ry] = move(arr, rx, ry, bx, by, i);
		}
	} else if (i === 1) {
		if (ry <= by) {
			[bx, by] = move(arr, bx, by, rx, ry, i);
			[rx, ry] = move(arr, rx, ry, bx, by, i);
		} else {
			[rx, ry] = move(arr, rx, ry, bx, by, i);
			[bx, by] = move(arr, bx, by, rx, ry, i);
		}
	} else if (i === 2) {
		if (rx <= bx) {
			[rx, ry] = move(arr, rx, ry, bx, by, i);
			[bx, by] = move(arr, bx, by, rx, ry, i);
		} else {
			[bx, by] = move(arr, bx, by, rx, ry, i);
			[rx, ry] = move(arr, rx, ry, bx, by, i);
		}
	} else {
		if (rx <= bx) {
			[bx, by] = move(arr, bx, by, rx, ry, i);
			[rx, ry] = move(arr, rx, ry, bx, by, i);
		} else {
			[rx, ry] = move(arr, rx, ry, bx, by, i);
			[bx, by] = move(arr, bx, by, rx, ry, i);
		}
	}

	return [rx, ry, bx, by];
};

const rec = (arr, rx, ry, bx, by, depth) => {
	// 기울인 횟수가 10 을 넘어가면 return
	if (depth > 10) return;

	// 파란 구슬이 구멍에 들어가면 return
	if (arr[bx][by] === "O") return;

	// 빨간 구슬만 구멍에 들어가면 depth 갱신
	if (arr[rx][ry] === "O") {
		ans = Math.min(ans, depth);

		return;
	}

	// 상, 하, 좌, 우로 만들 수 있는 모든 경우 만들어보기
	for (let i = 0; i < 4; i++) {
		const [nextRx, nextRy, nextBx, nextBy] = tilt(arr, rx, ry, bx, by, i);

		// 기울인 후에도 구슬의 위치가 변하지 않으면 continue
		if (nextRx === rx && nextRy === ry && nextBx === bx && nextBy === by)
			continue;

		rec(arr, nextRx, nextRy, nextBx, nextBy, depth + 1);
	}
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const arr = input.slice(1).map((v) => v.split(""));

	let [rx, ry] = [0, 0];
	let [bx, by] = [0, 0];

	// 빨간 구슬과 파란 구슬의 위치 찾기
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			if (arr[i][j] === "B") {
				arr[i][j] = ".";
				[bx, by] = [i, j];
			} else if (arr[i][j] === "R") {
				arr[i][j] = ".";
				[rx, ry] = [i, j];
			}
		}
	}

	rec(arr, rx, ry, bx, by, 0);

	// 10 번을 기울여도 빨간 구슬이 구멍에 빠지지 않는다면 -1 return
	if (ans === MAX) return -1;
	return ans;
};

console.log(solution(input));