Node.js) 백준 25383번: 주사위

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

25383번: 주사위

 

 

어제 다 푼 문제인데,  

 코드가 지저분하니까 어디서 잘못된건지를 잘 몰라서 이곳 저곳 수정하다가 겨우 에러가 발생하는 지점을 찾았다. 주사위 변형하는 부분에 오류가 있을 줄 알았는데, 제일 처음  주사위 만들 때  실수가 있었다. 오늘이라도 발견해서 다행이다. 

 

 

 

푼 사람이 별로 없는 문제라서

Node로 이 문제 푼 사람 중에 1등이다🙂. 벽이라고 느껴지던 플레 1문제를 혼자 힘으로 풀었다는 게 더 기쁘다

 

 

 

class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.length = 0;
	}

	push(item) {
		const node = new Node(item);
		if (this.head == null) {
			this.head = node;
		} else {
			this.tail.next = node;
		}

		this.tail = node;
		this.length += 1;
	}

	pop() {
		const popItem = this.head;
		this.head = this.head.next;
		this.length -= 1;
		return popItem.item;
	}
}

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.trim());
const [H, W] = input
	.shift()
	.split(' ')
	.map((v) => Number(v));

let board = input.map((v) => v.split(''));
// 위, 아래, 왼쪽, 오른쪽
// 입력에서 주사위 탐색할 때 쓰일 값.
const bdx = [-4, 4, 0, 0];
const bdy = [0, 0, -4, 4];

// 입력으로부터 새로운 주사위를 만들 때 사용할 값.
// 위 /4 하면 되는데,,, 그냥 만들어 줬음.
const ddx = [-1, 1, 0, 0];
const ddy = [0, 0, -1, 1];

// 깨끗하게 비교에 사용될 수 있도록 정돈된 주사위의 전개도를 담을 배열
const tidyDice = [];

// 각 주사위 모눈에 인덱스를 부여함.  Map<그림, 모눈인덱스>
/**
 *  ...           xxx
 *  ...  => 0     xxx => 511
 *  ...           xxx
 */
const symbolIndex = new Map();
for (let i = 0; i < 1 << 9; i++) {
	let x = i;
	let shift = 0;
	let symbol = '';
	while (shift < 9) {
		if ((x & (1 << shift)) != 0) {
			symbol += 'x';
		} else {
			symbol += '.';
		}
		shift++;
	}
	symbolIndex.set(symbol, i);
}

// 인덱스를 회전했을 때 어떤 인덱스가 되는지 확인하기 위한 맵
const symbols = new Map();
symbolIndex.forEach((value, key) => {
	const arr = [key.slice(0, 3).split(''), key.slice(3, 6).split(''), key.slice(6, 9).split('')];
	const rotated = rotate(arr)
		.map((v) => v.map((x) => x.join('')).join(''))
		.map((s) => symbolIndex.get(s));
	symbols.set(value, rotated);
});

/// 탐색가능한 주사위의 패턴  (11(정육면체 전개도 개수)*2(대칭) - (대칭해도 똑같은거) ) * 4(회전)
// 회전했을 때 원래 패턴이랑 같은 것도 있는데, 그 정도는 그냥 무시.
const dicePattern = [
	////////////////////////0
	[
		[0, 1, 0, 0],
		[1, 1, 1, 1],
		[0, 1, 0, 0],
	],
	///////////////////////////1
	[
		[1, 0, 0, 0],
		[1, 1, 1, 1],
		[1, 0, 0, 0],
	],
	/////////////////////////// 2 3
	[
		[0, 1, 0, 0],
		[1, 1, 1, 1],
		[1, 0, 0, 0],
	],
	[
		[1, 0, 0, 0],
		[1, 1, 1, 1],
		[0, 1, 0, 0],
	],
	///////////////////////////4 5
	[
		[0, 0, 1, 0],
		[1, 1, 1, 1],
		[1, 0, 0, 0],
	],
	[
		[1, 0, 0, 0],
		[1, 1, 1, 1],
		[0, 0, 1, 0],
	],
	/////////////////////////// 6 7
	[
		[0, 0, 0, 1],
		[1, 1, 1, 1],
		[1, 0, 0, 0],
	],
	[
		[1, 0, 0, 0],
		[1, 1, 1, 1],
		[0, 0, 0, 1],
	],

	/////////////////////////// 8 9
	[
		[0, 0, 1, 0],
		[1, 1, 1, 1],
		[0, 1, 0, 0],
	],
	[
		[0, 1, 0, 0],
		[1, 1, 1, 1],
		[0, 0, 1, 0],
	],
	///////////////////////////10 11
	[
		[0, 0, 1, 1],
		[0, 1, 1, 0],
		[1, 1, 0, 0],
	],
	[
		[1, 1, 0, 0],
		[0, 1, 1, 0],
		[0, 0, 1, 1],
	],
	/////////////////////////// 12 13
	[
		[0, 0, 1, 1],
		[1, 1, 1, 0],
		[1, 0, 0, 0],
	],
	[
		[1, 0, 0, 0],
		[1, 1, 1, 0],
		[0, 0, 1, 1],
	],
	/////////////////////////// 14 15
	[
		[0, 1, 0, 0],
		[0, 1, 1, 1],
		[1, 1, 0, 0],
	],
	[
		[1, 1, 0, 0],
		[0, 1, 1, 1],
		[0, 1, 0, 0],
	],
	/////////////////////////// 16 17
	[
		[0, 1, 0, 0],
		[1, 1, 1, 0],
		[0, 0, 1, 1],
	],
	[
		[0, 0, 1, 1],
		[1, 1, 1, 0],
		[0, 1, 0, 0],
	],
	/////////////////////////// 18 19
	[
		[0, 0, 1, 1, 1],
		[1, 1, 1, 0, 0],
	],

	[
		[1, 1, 1, 0, 0],
		[0, 0, 1, 1, 1],
	],
].map((v) => rotate(v));

// 각 패턴을 전부 0 번 꼴로 만들어 줄꺼임.
//      5
//    1 2 3 4
//      6
//

const transformDice = [
	(arr) => arr, //0
	(arr) => {
		//1
		arr[0][1] = symbols.get(arr[0][0])[1];
		arr[0][0] = -1;

		arr[2][1] = symbols.get(arr[2][0])[3];
		arr[2][0] = -1;
		return arr;
	},
	(arr) => {
		//2
		arr[2][1] = symbols.get(arr[2][0])[3];
		arr[2][0] = -1;
		return arr;
	},
	(arr) => {
		//3
		arr[0][1] = symbols.get(arr[0][0])[1];
		arr[0][0] = -1;
		return arr;
	},
	(arr) => {
		//4
		arr[0][1] = symbols.get(arr[0][2])[3];
		arr[0][2] = -1;
		arr[2][1] = symbols.get(arr[2][0])[3];
		arr[2][0] = -1;
		return arr;
	},
	(arr) => {
		//5
		arr[0][1] = symbols.get(arr[0][0])[1];
		arr[0][0] = -1;
		arr[2][1] = symbols.get(arr[2][2])[1];
		arr[2][2] = -1;
		return arr;
	},
	(arr) => {
		//6
		arr[0][1] = symbols.get(arr[0][3])[2];
		arr[0][3] = -1;

		arr[2][1] = symbols.get(arr[2][0])[3];
		arr[2][0] = -1;
		return arr;
	},
	(arr) => {
		//7
		arr[0][1] = symbols.get(arr[0][0])[1];
		arr[0][0] = -1;
		arr[2][1] = symbols.get(arr[2][3])[2];
		arr[2][3] = -1;
		return arr;
	},
	(arr) => {
		//8
		arr[0][1] = symbols.get(arr[0][2])[3];
		arr[0][2] = -1;
		return arr;
	},
	(arr) => {
		//9

		arr[2][1] = symbols.get(arr[2][2])[1];
		arr[2][2] = -1;
		return arr;
	},
	(arr) => {
		//10
		arr[1][0] = symbols.get(arr[2][0])[1];
		arr[2][0] = -1;

		arr[0][1] = symbols.get(arr[0][2])[3];
		arr[0][2] = -1;

		arr[1][3] = symbols.get(arr[0][3])[1];
		arr[0][3] = -1;
		return arr;
	},
	(arr) => {
		//11

		arr[1][0] = symbols.get(arr[0][0])[3];
		arr[0][0] = -1;

		arr[2][1] = symbols.get(arr[2][2])[1];
		arr[2][2] = -1;

		arr[1][3] = symbols.get(arr[2][3])[3];
		arr[2][3] = -1;
		return arr;
	},
	(arr) => {
		//12

		arr[0][1] = symbols.get(arr[0][2])[3];
		arr[0][2] = -1;

		arr[1][3] = symbols.get(arr[0][3])[1];
		arr[0][3] = -1;

		arr[2][1] = symbols.get(arr[2][0])[3];
		arr[2][0] = -1;
		return arr;
	},
	(arr) => {
		//13
		arr[0][1] = symbols.get(arr[0][0])[1];
		arr[0][0] = -1;
		arr[2][1] = symbols.get(arr[2][2])[1];
		arr[2][2] = -1;
		arr[1][3] = symbols.get(arr[2][3])[3];
		arr[2][3] = -1;
		return arr;
	},

	(arr) => {
		//14
		arr[1][0] = symbols.get(arr[2][0])[1];
		arr[2][0] = -1;
		return arr;
	},
	(arr) => {
		//15
		arr[1][0] = symbols.get(arr[0][0])[3];
		arr[0][0] = -1;
		return arr;
	},
	(arr) => {
		//16
		arr[1][3] = symbols.get(arr[2][3])[3];
		arr[2][3] = -1;

		arr[2][1] = symbols.get(arr[2][2])[1];
		arr[2][2] = -1;
		return arr;
	},
	(arr) => {
		//17
		arr[1][3] = symbols.get(arr[0][3])[1];
		arr[0][3] = -1;

		arr[0][1] = symbols.get(arr[0][2])[3];
		arr[0][2] = -1;
		return arr;
	},
	(arr) => {
		//18
		const newArr = [
			[-1, symbols.get(arr[1][0])[2], -1, -1],
			[symbols.get(arr[1][1])[1], arr[0][2], arr[0][3], arr[0][4]],
			[-1, arr[1][2], -1, -1],
		];
		return newArr;
	},
	(arr) => {
		//19
		const newArr = [
			[-1, arr[0][2], -1, -1],
			[symbols.get(arr[0][1])[3], arr[1][2], arr[1][3], arr[1][4]],
			[-1, symbols.get(arr[0][0])[2], -1, -1],
		];
		return newArr;
	},
];

// 시계방향으로 회전된 배열을 4개 반환하는 함수
function rotate(arr1) {
	const r = arr1.length;
	const c = arr1[0].length;

	const arr2 = Array.from(Array(c), () => Array(r));
	for (let i = 0; i < r; i++) {
		for (let j = 0; j < c; j++) {
			arr2[j][r - i - 1] = arr1[i][j];
		}
	}

	const arr3 = Array.from(Array(r), () => Array(c));
	for (let i = 0; i < r; i++) {
		for (let j = 0; j < c; j++) {
			arr3[r - i - 1][c - j - 1] = arr1[i][j];
		}
	}
	const arr4 = Array.from(Array(c), () => Array(r));
	for (let i = 0; i < r; i++) {
		for (let j = 0; j < c; j++) {
			arr4[c - j - 1][i] = arr1[i][j];
		}
	}
	return [arr1, arr2, arr3, arr4];
}

// 주사위 그림에 따른  모눈인덱스를 찾아주는 함수
function getSymbol(i, j) {
	let symbol = '';
	symbol += board[i + 1][j + 1] + board[i + 1][j + 2] + board[i + 1][j + 3];
	symbol += board[i + 2][j + 1] + board[i + 2][j + 2] + board[i + 2][j + 3];
	symbol += board[i + 3][j + 1] + board[i + 3][j + 2] + board[i + 3][j + 3];
	return symbol;
}

// 주사위 면이 맞는지 검사
function isDiceFace(i, j) {
	return (
		i >= 0 &&
		j >= 0 &&
		i + 4 < H &&
		j + 4 < W &&
		board[i][j] == '+' &&
		board[i][j + 1] == '-' &&
		board[i + 1][j] == '|' &&
		board[i][j + 4] == '+' &&
		board[i][j + 3] == '-' &&
		board[i + 1][j + 4] == '|' &&
		board[i + 4][j] == '+' &&
		board[i + 4][j + 1] == '-' &&
		board[i + 3][j] == '|' &&
		board[i + 4][j + 4] == '+' &&
		board[i + 4][j + 3] == '-' &&
		board[i + 3][j + 4] == '|' &&
		board[i + 1][j + 1] != 'o'
	);
}

function checkPattern(pattern, dice) {
	const r = pattern.length;
	const c = pattern[0].length;
	for (let i = 0; i < r; i++) {
		for (let j = 0; j < c; j++) {
			if ((pattern[i][j] == 1 && dice[i][j] == -1) || (pattern[i][j] == 0 && dice[i][j] >= 0))
				return false;
		}
	}
	return true;
}

function convertToFirstPattern(arr, cnt) {
	while (cnt < 4) {
		const r = arr.length;
		const c = arr[0].length;
		let rotatedArr = Array.from(Array(c), () => Array(r).fill(-1));
		for (let i = 0; i < r; i++) {
			for (let j = 0; j < c; j++) {
				if (arr[i][j] > -1) rotatedArr[j][r - i - 1] = symbols.get(arr[i][j])[1];
			}
		}
		arr = rotatedArr;
		cnt++;
	}
	return arr;
}

// Main은
//   5
// 1 2 3 4
//   6          중에서 2의자리
//
// 다른 숫자도 2의 자리에 있는 형태로 만들어서 총 6개의 주사위 전개도를 반환
function changeMainFace(arr) {
	const arr1 = arr;

	const arr2 = [
		[-1, symbols.get(arr[0][1])[1], -1, -1],
		[arr[1][1], arr[1][2], arr[1][3], arr[1][0]],
		[-1, symbols.get(arr[2][1])[3], -1, -1],
	];

	const arr3 = [
		[-1, symbols.get(arr[0][1])[2], -1, -1],
		[arr[1][2], arr[1][3], arr[1][0], arr[1][1]],
		[-1, symbols.get(arr[2][1])[2], -1, -1],
	];

	const arr4 = [
		[-1, symbols.get(arr[0][1])[3], -1, -1],
		[arr[1][3], arr[1][0], arr[1][1], arr[1][2]],
		[-1, symbols.get(arr[2][1])[1], -1, -1],
	];
	const arr5 = [
		[-1, symbols.get(arr[1][3])[2], -1, -1],
		[symbols.get(arr[1][0])[1], arr[0][1], symbols.get(arr[1][2])[3], symbols.get(arr[2][1])[2]],
		[-1, arr[1][1], -1, -1],
	];

	const arr6 = [
		[-1, arr[1][1], -1, -1],
		[symbols.get(arr[1][0])[3], arr[2][1], symbols.get(arr[1][2])[1], symbols.get(arr[0][1])[2]],
		[-1, symbols.get(arr[1][3])[2], -1, -1],
	];

	return [
		...rotateMainFace(arr1),
		...rotateMainFace(arr2),
		...rotateMainFace(arr3),
		...rotateMainFace(arr4),
		...rotateMainFace(arr5),
		...rotateMainFace(arr6),
	];
}

// Main 기준으로 회전하는 함수  총 4개의 변형된 주사위 전개도를 반환
function rotateMainFace(arr) {
	const arr1 = arr;

	const arr2 = [
		[-1, symbols.get(arr[1][2])[3], -1, -1],
		[
			symbols.get(arr[0][1])[3],
			symbols.get(arr[1][1])[3],
			symbols.get(arr[2][1])[3],
			symbols.get(arr[1][3])[1],
		],
		[-1, symbols.get(arr[1][0])[3], -1, -1],
	];

	const arr3 = [
		[-1, symbols.get(arr[2][1])[2], -1, -1],
		[
			symbols.get(arr[1][2])[2],
			symbols.get(arr[1][1])[2],
			symbols.get(arr[1][0])[2],
			symbols.get(arr[1][3])[2],
		],
		[-1, symbols.get(arr[0][1])[2], -1, -1],
	];

	const arr4 = [
		[-1, symbols.get(arr[1][0])[1], -1, -1],
		[
			symbols.get(arr[2][1])[1],
			symbols.get(arr[1][1])[1],
			symbols.get(arr[0][1])[1],
			symbols.get(arr[1][3])[3],
		],
		[-1, symbols.get(arr[1][2])[1], -1, -1],
	];

	return [arr1, arr2, arr3, arr4];
}

const diceInfo = [];
for (let i = 0; i < H; i++) {
	for (let j = 0; j < W; j++) {
		if (isDiceFace(i, j)) {
			let dice = Array.from(Array(9), () => Array(9).fill(-1));
			dice[4][4] = symbolIndex.get(getSymbol(i, j));
			board[i + 1][j + 1] = 'o';

			const q = new Queue();
			q.push([i, j, 4, 4]);
			while (q.length > 0) {
				const [boardX, boardY, diceX, diceY] = q.pop();

				for (let k = 0; k < 4; k++) {
					const nbx = boardX + bdx[k];
					const nby = boardY + bdy[k];
					const ndx = diceX + ddx[k];
					const ndy = diceY + ddy[k];

					if (isDiceFace(nbx, nby)) {
						dice[ndx][ndy] = symbolIndex.get(getSymbol(nbx, nby));
						board[nbx + 1][nby + 1] = 'o';
						q.push([nbx, nby, ndx, ndy]);
					}
				}
			}
			while (dice.length > 0) {
				let zero = true;
				for (let k = 0; k < dice[0].length; k++) {
					if (dice[0][k] >= 0) {
						zero = false;
						break;
					}
				}
				if (zero) {
					dice.shift();
				} else {
					break;
				}
			}
			while (dice.length > 0) {
				let zero = true;
				for (let k = 0; k < dice[0].length; k++) {
					if (dice[dice.length - 1][k] >= 0) {
						zero = false;
						break;
					}
				}
				if (zero) {
					dice.pop();
				} else {
					break;
				}
			}

			while (true) {
				let zero = true;
				for (let i = 0; i < dice.length; i++) {
					if (dice[i][0] >= 0) {
						zero = false;
						break;
					}
				}
				if (zero) {
					for (let i = 0; i < dice.length; i++) {
						dice[i].shift();
					}
				} else {
					break;
				}
			}

			while (true) {
				let zero = true;
				for (let i = 0; i < dice.length; i++) {
					if (dice[i][dice[i].length - 1] >= 0) {
						zero = false;
						break;
					}
				}
				if (zero) {
					for (let i = 0; i < dice.length; i++) {
						dice[i].pop();
					}
				} else {
					break;
				}
			}

			let findPattern = false;
			for (let i = 0; i < dicePattern.length; i++) {
				if (findPattern) break;
				for (let j = 0; j < 4; j++) {
					const pattern = dicePattern[i][j];
					const patternRow = pattern.length;
					const patternColumn = pattern[0].length;

					const diceRow = dice.length;
					const diceCoulum = dice[0].length;
					if (patternRow != diceRow || patternColumn != diceCoulum) continue;
					if (checkPattern(pattern, dice)) {
						diceInfo.push([i, j]);
						tidyDice.push(
							changeMainFace(transformDice[i](convertToFirstPattern(dice, j)))
								.map((v) => {
									let str = v[0][1].toString(2).padStart(9, '0');
									str += v[1][0].toString(2).padStart(9, '0');
									str += v[1][1].toString(2).padStart(9, '0');
									str += v[1][2].toString(2).padStart(9, '0');
									str += v[1][3].toString(2).padStart(9, '0');
									str += v[2][1].toString(2).padStart(9, '0');
									return str;
								})
								.sort()[0]
						);

						findPattern = true;
						break;
					}
				}
			}
		}
	}
}

const answerMap = new Map();
for (let i = 0; i < tidyDice.length; i++) {
	if (answerMap.has(tidyDice[i])) {
		const cnt = answerMap.get(tidyDice[i]);
		answerMap.set(tidyDice[i], cnt + 1);
	} else {
		answerMap.set(tidyDice[i], 1);
	}
}

const answer = [...answerMap]
	.sort((a, b) => b[1] - a[1])
	.map((v) => String(v[1]))
	.join(' ');
console.log(answer);