🔒 문제
🧠 아이디어
90도 회전처리
퍼즐이 빈 부분 없이 맞는지 확인하기 위해서
90도, 180도, 270도로 3회 회전하는 로직이 필요하다.
퍼즐을 맞추는 순서는 상관이 없다.
퍼즐 조각 사이즈 일치여부 확인
한 칸이라도 초과하거나 남으면 안되기 때문에 퍼즐크기가 완전히 일치하는 것 끼리만 확인한다.
(0,0) 으로 평행 이동하여 일치여부 확인
game_board 와 table 상의 좌표상에서 바로 비교하기 까다로우므로
(0,0) 을 기준으로 퍼즐 조각을 평행이동 시켜서 퍼즐조각이 맞는지 확인한다.
평행이동시 맨 왼쪽 윗칸 (0,0) 부터 행과 열번호를 증가시키며~~ BFS 시작 지점좌표를 빼면 된다.~~
구한 좌표 값을 넣어놓고 행과 열 최소값을 빼면된다.
그리고 game_board 에서 구한 원본을 0,1 미리 반전시켜두면 table 로 부터 구한 퍼즐이 완벽히 일치하는지 쉽게 확인할 수 있다.
BFS 활용하기
game_board 는 맨 (0,0)으로부터 0을
table 은 (0,0)으로부터 1을 찾아 퍼즐조각을 1개만 포함한 정사각형을 생성하면 된다.
행과 열 중 길이가 더 큰 값으로 정사각형 찍어 넣기
퍼즐 조각 사이즈를 key, 정사각형을 value 로 두면 비교하기 쉽다.
정사각형으로 퍼즐조각을 keep 하면 안된다.
⚠️ 퍼즐조각들을 정사각형으로 강제하면 안되는 이유
🔑 풀이
import java.util.*
enum class TableType {
GAME_BOARD,
TABLE
}
class Puzzle {
// key: 점의 개수. value: (0,0)으로 평행이동시킨 정사각형 퍼즐조각
private val originBoardMap = HashMap<Int, MutableList<Array<IntArray>>>()
private val puzzleTableMap = HashMap<Int, MutableList<Array<IntArray>>>()
private val queue : Queue<IntArray> = LinkedList<IntArray>()
private val dx = intArrayOf(1, 0, -1, 0)
private val dy = intArrayOf(0, 1, 0, -1)
private fun rotateSquare(puzzleTable: Array<IntArray>) : Array<IntArray> {
val rowSize = puzzleTable.size
val colSize = puzzleTable[0].size
val rotatedMatrix = Array(colSize){IntArray(rowSize)}
for (rowIdx in puzzleTable.indices) {
for (colIdx in puzzleTable[rowIdx].indices) {
rotatedMatrix[colIdx][rowIdx] = puzzleTable[rowSize - 1 - rowIdx][colIdx]
}
}
return rotatedMatrix
}
private fun isMatched(puzzleTable: Array<IntArray>, rotatedMatrix: Array<IntArray>) : Boolean {
if (puzzleTable.size != rotatedMatrix.size || puzzleTable[0].size != rotatedMatrix[0].size) return false
for (rowIdx in puzzleTable.indices) {
if (!puzzleTable[rowIdx].contentEquals(rotatedMatrix[rowIdx])) return false
}
return true
}
private fun makeMovedSquare(squarePoints: ArrayList<IntArray>, tableType: TableType) {
val minRow = squarePoints.minOf { it.first() }
val minCol = squarePoints.minOf { it.last() }
val rowSize = squarePoints.maxOf { it.first() - minRow + 1 }
val colSize = squarePoints.maxOf { it.last() - minCol + 1 }
// 평행이동한 2차원 배열 생성 (0으로 초기화)
// 직사각형
val gameBoard = Array(rowSize){IntArray(colSize)}
for (point in squarePoints) {
val (row, col) = point
// 좌표 찍힌 애들은 전부 여기 1로 표시
gameBoard[row - minRow][col - minCol] = 1
}
// tableType 0: game_board, 1: Table
if (tableType == TableType.GAME_BOARD) {
// 점의 개수로 key
val originBoardList = originBoardMap.getOrDefault(squarePoints.size, mutableListOf())
originBoardList.add(gameBoard)
originBoardMap[squarePoints.size] = originBoardList
} else {
val puzzleTableList = puzzleTableMap.getOrDefault(squarePoints.size, mutableListOf())
puzzleTableList.add(gameBoard)
puzzleTableMap[squarePoints.size] = puzzleTableList
}
}
private fun bfs(startRowIdx: Int, startColIdx: Int, findValue: Int, puzzleTable: Array<IntArray>, visited: Array<BooleanArray>) {
// 정사각형 생성 로직 필요함 (0,0) 기준
val squarePoints = ArrayList<IntArray>()
queue.add(intArrayOf(startRowIdx, startColIdx))
visited[startRowIdx][startColIdx] = true
squarePoints.add(intArrayOf(startRowIdx, startColIdx))
// 행과 열중 최소값을 0,0 이동을 위한
while (queue.isNotEmpty()) {
val (curRowIdx, curColIdx) = queue.poll()
// 남동북서 다음 노드 확인
for (i in dx.indices) {
val nextRowIdx = curRowIdx + dx[i]
val nextColIdx = curColIdx + dy[i]
// 범위를 벗어나면 skip
if (nextRowIdx < 0 || nextRowIdx >= puzzleTable.size || nextColIdx < 0 || nextColIdx >= puzzleTable[0].size) continue
// 이미 방문한 위치도 skip
if (visited[nextRowIdx][nextColIdx]) continue
if (puzzleTable[nextRowIdx][nextColIdx] == findValue) {
visited[nextRowIdx][nextColIdx] = true
queue.add(intArrayOf(nextRowIdx, nextColIdx))
squarePoints.add(intArrayOf(nextRowIdx, nextColIdx))
}
}
}
// 일단 1라운드 끝날 때 마다 여기서 생성된 애들을 정사각형으로 찍어낸다.
if (findValue == 0) makeMovedSquare(squarePoints, TableType.GAME_BOARD)
else makeMovedSquare(squarePoints, TableType.TABLE)
}
fun solution(game_board: Array<IntArray>, table: Array<IntArray>): Int {
var answer = 0
// game board 돌면서 사이즈별 (0,0) 로 초기화된 메트릭스 생성
val gameBoardVisited = Array(game_board.size){BooleanArray(game_board.size){false}}
val tableVisited = Array(table.size){BooleanArray(table.size){false} }
for (rowIdx in game_board.indices) {
for (colIdx in game_board[rowIdx].indices) {
if (!gameBoardVisited[rowIdx][colIdx] && game_board[rowIdx][colIdx] == 0) {
bfs(rowIdx, colIdx, 0, game_board, gameBoardVisited)
}
if (!tableVisited[rowIdx][colIdx] && table[rowIdx][colIdx] == 1) {
bfs(rowIdx, colIdx, 1, table, tableVisited)
}
}
}
for (pointCnt in puzzleTableMap.keys) {
for (tablePuzzle in puzzleTableMap[pointCnt]!!) {
var rotatedPuzzle = tablePuzzle
for (cnt in 0 .. 3) {
rotatedPuzzle = rotateSquare(rotatedPuzzle)
var isFindMatchedPuzzle = false
// Avoid current modification
if(originBoardMap[pointCnt] != null) {
for (originalMatrix in originBoardMap[pointCnt]!!) {
if (isMatched(originalMatrix, rotatedPuzzle)) {
answer += pointCnt
originBoardMap[pointCnt]!!.remove(originalMatrix)
isFindMatchedPuzzle = true
break
}
}
}
if(isFindMatchedPuzzle) break
}
}
}
return answer
}
}
I'm still hungry