[Programmers] 퍼즐 조각 채우기

Falcon·2022년 9월 30일
1

programmers

목록 보기
25/27
post-thumbnail
post-custom-banner

🔒 문제

🧠 아이디어

90도 회전처리

퍼즐이 빈 부분 없이 맞는지 확인하기 위해서
90도, 180도, 270도로 3회 회전하는 로직이 필요하다.

퍼즐을 맞추는 순서는 상관이 없다.

퍼즐 조각 사이즈 일치여부 확인

한 칸이라도 초과하거나 남으면 안되기 때문에 퍼즐크기가 완전히 일치하는 것 끼리만 확인한다.

(0,0) 으로 평행 이동하여 일치여부 확인

game_boardtable 상의 좌표상에서 바로 비교하기 까다로우므로
(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
    }
}
profile
I'm still hungry
post-custom-banner

0개의 댓글