[백준] 14600 샤워실 바닥 깔기 (Small) - js

January 02, 2024

ALGORITHM

오늘은 민규가 훈련소에 입소하는 날이다. 모든 행사를 마치고 생활관으로 돌아와서 쉬려는데 갑자기 교관이 들어오더니 민규의 이름을 부르는 것이 아닌가. 당황한 채로 따라갔더니 이번엔 김준서를 아느냐고 물어보았다. 그 녀석이 샤워실 바닥을 깔았는데, 배수구 위치까지 막아버렸다면서 같은 학교 출신인 민규가 다시 깔라는 것이었다.

어떻게 타일을 깔지 고민하던 민규는 샤워실의 구조가 정사각형이면서 한 변의 길이가 2의 제곱수라는 사실을 알아냈다. 준서는 여기까지만 고려해서 2x2 크기의 타일로 바닥을 전부 채운 것 같은데, 문제는 이렇게 하면 배수구가 있어야 할 위치를 비울 수가 없다는 것이다. 이런저런 방법을 생각하다가 4칸을 차지하는 정사각형 타일 대신 3칸을 차지하는 ㄱ자 모양의 타일을 사용하면 될 것 같다는 느낌을 받았다.

그런데 ㄱ자 타일을 어떻게 채워야 할까? 생각하다 지친 민규는 여러분에게 이 방법을 찾아달라고 부탁했다. 첫날부터 생활관에서 밤을 새우는 일이 없도록 여러분이 도와주자.

접근

핵심은 2x2(4칸) 크기의 타일을 배치하기 보다는 ㄱ자(3칸) 타일들을 배치해서 바닥을 채워야 하는 것 이다.

만들어질 수 있는 ㄱ자 타일들은 ㄱ자로 만들 수 있는 2가지와 ㄴ자로 만들 수 있는 2가지 총 4가지로 분류된다.

그렇기 때문에 이를 컴퓨터가 이해할 수 있게끔 좌표로 표현해보면 다음과 같이 표현할 수 있겠다.


const ORIGN = [
	// ㄱ자
	[0, 0],
	[0, 1],
	[1, 1],
];

const ORIGN_REVERSED = [
	// ㄱ자 뒤집은 형태
	[0, 0],
	[0, 1],
	[1, 0],
];

const REVERSED = [
	// ㄴ자
	[0, 0],
	[1, 0],
	[1, 1],
];

const REVERSED_REVERSED = [
	// ㄴ자 뒤집은 형태
	[0, 0],
	[1, 0],
	[1, -1],
];

이렇게 표현된 타일들로 차곡차곡 타일을 배치했을 때 만약 이것들로 채울 수 없다면 falsy 값를 채울 수 있다면 true 값을 리턴하면 되겠다.

채우는 동안에 특정 타일을 채울 수 없으면 다음 타일을 사용해서 바닥을 계속해서 채우기 때문에 이러한 특성을 갖는 backtracking 알고리즘을 활용하면 문제를 풀 수 있겠다.

바닥은 정사각형 모양이기 때문에 해당 정사각형 공간을 넘어서서 타일을 배치할 수 없다. 때문에 이를 처리해주는 isOutOfRange 함수를 통해 이를 감지하도록 한다.


const N = 2 ** K; // K는 입력으로 주어지고, 이는 한 변의 길이를 의미한다고 문제에서 주어진다.

function isOutofRange(r, c) {
	if (r >= 0 && r < N && c >= 0 && c < N) return false;
	return true;
}

isOutOfRange 함수를 통해 만약 현재 좌표가 바닥의 크기를 넘어간다면 타일을 배치하지 않고, 다음 좌표로 넘어갈 수 있게 해주고 아니라면 바닥에 타일을 깔면 되겠다.

이러한 설계를 바탕으로 코드를 작성하기만 하면 문제를 풀 수 있다.

코드


let fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'test.txt';
let input = fs
	.readFileSync(filePath)
	.toString()
	.trim()
	.split('\n')
	.map((str) => str.replace('\r', ''));

const K = +input[0];
const N = 2 ** K;
const [x, y] = input[1].split(' ').map(Number);

const ORIGN = [
	[0, 0],
	[0, 1],
	[1, 1],
];

const ORIGN_REVERSED = [
	[0, 0],
	[0, 1],
	[1, 0],
];

const REVERSED = [
	[0, 0],
	[1, 0],
	[1, 1],
];

const REVERSED_REVERSED = [
	[0, 0],
	[1, 0],
	[1, -1],
];

const isHole = -1;

const floor = Array(N)
	.fill(null)
	.map((_) => Array(N).fill(0));

floor[y - 1][x - 1] = isHole;

function isOutofRange(r, c) {
	if (r >= 0 && r < N && c >= 0 && c < N) return false;
	return true;
}

function backtracking(r, c, floor, count) {
	/** return 의 조건
	 * 1. r === K - 1 || c === K - 1
	 * 2. c 가 현재 범위를 넘을 때
	 * 3. r 이 현재 범위를 넘을 때 <- 얘는 1번 조건에서 닿아 리턴되기 때문에 그냥 pass
	 * 4. 현재 공간은 체크할 필요 없어 넘어갈 때
	 * 4-1. 이는 2가 될 수 있고
	 * 4-2. 아니면 그냥 오른쪽으로 넘어갈 수 있음
	 */

	if (r === N - 1 && c === N - 1) {
		floor.reverse();

		console.log(floor.map((item) => item.join(' ')).join('\n'));
		return true;
	}

	if (floor[r][c] || floor[r][c] === isHole) {
		if (c + 1 === N) {
			return backtracking(r + 1, 0, floor, count);
		} else {
			return backtracking(r, c + 1, floor, count);
		}
	}

	if (isOutofRange(r, c)) {
		if (c === N) return backtracking(r + 1, 0, floor, count);

		return backtracking(r, c + 1, floor, count);
	}

	let result;
	let isOriginPossible = true;
	let isOriginReversePossible = true;
	let isReversePossible = true;
	let isReverseReversePossible = true;

	for (const [dr, dc] of ORIGN) {
		const nr = r + dr;
		const nc = c + dc;

		if (!isOutofRange(nr, nc) && !floor[nr][nc]) continue;
		isOriginPossible = false;
	}

	if (isOriginPossible) {
		for (const [dr, dc] of ORIGN) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = count;
		}

		result = backtracking(r, c + 1, floor, count + 1);
		if (result) return result;

		for (const [dr, dc] of ORIGN) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = 0;
		}
	}

	for (const [dr, dc] of REVERSED) {
		const nr = r + dr;
		const nc = c + dc;

		if (!isOutofRange(nr, nc) && !floor[nr][nc]) continue;
		isReversePossible = false;
	}

	if (isReversePossible) {
		for (const [dr, dc] of REVERSED) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = count;
		}

		result = backtracking(r, c + 1, floor, count + 1);
		if (result) return result;

		for (const [dr, dc] of REVERSED) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = 0;
		}
	}

	for (const [dr, dc] of ORIGN_REVERSED) {
		const nr = r + dr;
		const nc = c + dc;

		if (!isOutofRange(nr, nc) && !floor[nr][nc]) continue;
		isOriginReversePossible = false;
	}

	if (isOriginReversePossible) {
		for (const [dr, dc] of ORIGN_REVERSED) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = count;
		}

		result = backtracking(r, c + 1, floor, count + 1);
		if (result) return result;

		for (const [dr, dc] of ORIGN_REVERSED) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = 0;
		}
	}

	for (const [dr, dc] of REVERSED_REVERSED) {
		const nr = r + dr;
		const nc = c + dc;

		if (!isOutofRange(nr, nc) && !floor[nr][nc]) continue;
		isReverseReversePossible = false;
	}

	if (isReverseReversePossible) {
		for (const [dr, dc] of REVERSED_REVERSED) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = count;
		}

		result = backtracking(r, c + 1, floor, count + 1);
		if (result) return result;

		for (const [dr, dc] of REVERSED_REVERSED) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = 0;
		}
	}

	return result;
}

const result = backtracking(0, 0, floor, 1);

if (!result) console.log(-1);

느낀점

코드를 보면 반복적인 코드가 보인다.

타일을 깔 때 동일한 코드가 반복되기 때문에 중복되는 코드들을 하나의 함수로 처리할 수 있겠다.

여기서 다른 부분은 flag 역할을 하는 is- 값과 타일의 위치를 담은 배열이다. 때문에 이를 묶어서 하나의 배열로 선언한 뒤 순회시키기만 한다면 코드를 획기적으로 줄일 수 있어 보였다.


const Tiles = [ORIGN, ORIGN_REVERSED, REVERSED, REVERSED_REVERSED];

for (const Tile of Tiles) {
	let isPossible = true;

	for (const [dr, dc] of Tile) {
		const nr = r + dr;
		const nc = c + dc;

		if (!isOutofRange(nr, nc) && !floor[nr][nc]) continue;
		isPossible = false;
	}

	if (isPossible) {
		for (const [dr, dc] of Tile) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = count;
		}

		result = backtracking(r, c + 1, floor, count + 1);
		if (result) return result;

		for (const [dr, dc] of Tile) {
			const nr = r + dr;
			const nc = c + dc;

			floor[nr][nc] = 0;
		}
	}
}

이렇게 처리하면 반복되던 4 개의 처리 과정을 for문 하나로 압축할 수 있겠다.

해당 문제는 생각보다 쉬운 문제였는지 질문 게시판에 어떠한 질문도 남겨있지 않았다. 다만 오랜만에 풀이하는 완전탐색 - 백트랙킹 유형의 문제였고, 가지치기 과정에서 보통은 2개 조건만 주어지는데 이번에는 4개의 조건(타일)이 주어져 문제풀이에 시간이 다소 소요되고 말았다.