[백준] 18808 스티커 붙이기

 

🔒 문제

 

 

🧠 아이디어

스티커를 포함한 모든 모눈 종이는 결국 직사각형 형태다.

바탕이 될 노트북 모눈종이판을 'noteBookTable' 스티커 조각들을 'sticker' 라고하면

 

1. 스티커 붙이기 가능 불가능 여부 판별법

다음 4가지 케이스가 존재한다.

1. ✔️noteBookTable 에서는 0 (비어있고) sticker 에서는 1 (스티커)
2. ✔️noteBookTable 에서는 1 (이미 다른 스티커가 붙어있고) sticker 에서는 0 (공백) 
3. ✔️noteBookTable 도 0 (비어있고) sticker 에서도 0
4. ❌noteBookTable 에서 1 (이미 다른 스티커가 붙어있고) sticker 에서도 1 (스티커)

위 케이스중 1,2,3 번만 스티커 붙이기가 가능한 케이스다.

noteBookTable과  sticker가 0-1, 1-0, 0-0 관계여야 하므로 NOR 연산이 true 면 붙일 수 있는 공간이다.

즉 같은 noteBookTable 과 sticker 사이에 모든 공간이 NOR == true 면 스티커 붙이기가 가능하다.

 

2. 스티커를 어디에 붙일지 어떻게 결정할 수 있을까?

우선, sticker 의 가로 또는 세로 길이가 noteBookTable 보다 더 긴 경우 무조건 실패다. 

직사각형을 맨 왼쪽 윗칸인 (0,0) 을 시작으로 한칸씩 이동하면서 붙여보는 수 밖에 없다. => Backtracking 으로 접근한다.

(스티커는 가능한 좌측 상단부터 붙인다고 설명되어있다.)

 

3. 노트북 - 스티커 조각 비교를 위한 조각 만들기

노트북 모눈종이와 스티커 조각의 가로 세로 길이가 다르므로 같은 길이의 조각을 추출해서 비교해주자.
이 때, 모눈종이에서 추출할 수 있는 가로 세로 길이가 스티커보다 작을 경우 해당 조각 생성은 skip 한다.

2차원 배열을 복사할 때 주의할 점은 여기에서 확인할 수 있다.

// 동일한 노트북 모눈종이로부터 스티커 크기와 동일한 사이즈의 직사각형 추출
private fun makePartialNoteBook(
    startRow: Int,
    startCol: Int,
    noteBookTable: Array<IntArray>,
    sticker: Array<IntArray>
): Array<IntArray> {
    val stickerRowSize = sticker.size
    val stickerColSize = sticker.first().size

    return Array(stickerRowSize) { idx ->
    // 해당 노트북의 시작지점으로부터 붙일 스티커의 크기만큼의 배열을 통째로 복사한다.
        noteBookTable[idx + startRow].copyOfRange(
            startCol,
            startCol + stickerColSize
        )
    }
}

 

 

4. 스티커 조각 90도 회전

2차원 배열 (행렬) 회전 방법은 여기에 정리해놓았다.

// 스티커 배열 90도 회전 후 반환
private fun rotateSticker(sticker: Array<IntArray>): Array<IntArray> {
    val originalRowSize = sticker.size
    val originalColSize = sticker.first().size

    val rotatedSticker = Array(originalColSize){IntArray(originalRowSize)}

    for (row in sticker.indices) {
        for (col in sticker[0].indices) {
            rotatedSticker[col][row] = sticker[originalRowSize - 1 - row][col]
        }
    }

    return rotatedSticker
}

 

5. 스티커 붙이기

위 1,2,3,4 아이디어로 스티커 붙이기가 가능한 케이스를 만났을 때, 모눈종이 원본에 색칠해주는 작업이 필요하다.

해당 시작 지점으로부터 생성했던 조각 크기만큼의 범위를 잡아 OR연산 결과값을 붙여넣는다.

 

 

6. 1~5를 반복하라, 언제까지?

모든 스티커 붙이기를 시도해보기까지

각 자리를 모두 탐색한 후에 90도 회전후 재시도해야한다.
한 자리에서 90, 180, 270도를 모두 회전시켜보는게 아니다.

문제를 꼼꼼히 읽지 않고 자리를 이동하며 (0도, 90도, 180도, 270도) 회전시켜보며 대입했다가 계속 틀렸다.

"테스트케이스는 다 맞는데 왜 뭐가 문제지?" 하면서 헤메다가 문제를 다시 읽고 알았다..

모든 자리에서 스티커 붙이기에 실패했을 때만 한 번 회전시키고 다시 자리를 찾아봐야한다.

 

🔑  Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private fun isOutOfBoundPartialTable(startRow: Int, startCol: Int, noteBookTable: Array<IntArray>, sticker: Array<IntArray>) : Boolean {
    val stickerRowSize = sticker.size
    val stickerColSize = sticker.first().size

    return startRow + stickerRowSize > noteBookTable.size || startCol + stickerColSize > noteBookTable.first().size
}


// 동일한 노트북 모눈종이로부터 스티커 크기와 동일한 사이즈의 직사각형 추출
private fun makePartialNoteBook(
    startRow: Int,
    startCol: Int,
    noteBookTable: Array<IntArray>,
    sticker: Array<IntArray>
): Array<IntArray> {
    val stickerRowSize = sticker.size
    val stickerColSize = sticker.first().size

    return Array(stickerRowSize) { idx ->
        noteBookTable[idx + startRow].copyOfRange(
            startCol,
            startCol + stickerColSize
        )
    }
}

private fun isAttachable(partialTable: Array<IntArray>, sticker: Array<IntArray>) : Boolean {
    for (row in partialTable.indices) {
        for (col in partialTable[row].indices) {
            // nor 이 false 면 스티커 붙이기 불가능 == 둘다 이미 채워져있는 칸이면
            if (partialTable[row][col] == 1 && sticker[row][col] == 1) return false
        }
    }
    // nor 연산 모두 통과시 스티커 붙이기 가능.
    return true
}

private fun rotateSticker(sticker: Array<IntArray>): Array<IntArray> {
    val originalRowSize = sticker.size
    val originalColSize = sticker.first().size

    val rotatedSticker = Array(originalColSize){IntArray(originalRowSize)}

    for (row in sticker.indices) {
        for (col in sticker[0].indices) {
            rotatedSticker[col][row] = sticker[originalRowSize - 1 - row][col]
        }
    }

    return rotatedSticker
}


fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val (N, M, K) = bufferedReader.readLine().split(" ").map(String::toInt)

    // 빈 노트북 테이블 생성
    val noteBookTable = Array(N){IntArray(M)}

    val stickerTable = LinkedList<Array<IntArray>>()

    // 스티커 생성
    for (i in 1 .. K) {
        val (rowSize, colSize) = bufferedReader.readLine().split(" ").map(String::toInt)
        val sticker = Array(rowSize){_->
            bufferedReader.readLine().split(" ").map(String::toInt).toIntArray()
        }
        stickerTable.add(sticker)
    }

    // 스티커 하나씩 꺼내서 비교
    for (sticker in stickerTable) {
        var isPasted = false
        var rotatedSticker = sticker

        for (repeatNum in 1 .. 4) {

            // 시작좌표 구하는 과정에서 1회라도 스티커 붙이기 성공시 탈출 (break)
            for (row in noteBookTable.indices) {
                if (isPasted) break

                for (col in noteBookTable[0].indices) {
                    // 추출이 가능한 크기의 스티커인지
                    if (isOutOfBoundPartialTable(row, col, noteBookTable, rotatedSticker)) continue
                    // 원본 모눈종이 조각 생성
                    val partTable = makePartialNoteBook(row, col, noteBookTable, rotatedSticker)
                    // 스티커 붙이기 가능여부 확인
                    if(!isAttachable(partTable, rotatedSticker)) continue

                    // 스티커 붙이기
                    for (i in row until row + rotatedSticker.size) {
                        for (j in col until col + rotatedSticker[0].size) {
                            // OR 연산의 결과를 그대로 붙여넣음.
                            noteBookTable[i][j] = noteBookTable[i][j] or rotatedSticker[i - row][j - col]
                        }
                    }
//                     붙이기가 완료되면 다음 스티커로 이동
                    isPasted = true
                    break
                }
            }
            //  도중에 스티커 붙이기 성공시 다음 회전 loop 에서 탈출 여기에 도달하지 않음.
            if (isPasted) break

            // 0도 -> 90도 -> 180도 -> 270도로 회전 총 4회,
            rotatedSticker = rotateSticker(rotatedSticker)
        }

    }

    // 모든 스티커 붙이기가 완료된 상태
    var emptyCnt = 0
    for (row in noteBookTable) {
        emptyCnt += row.count{it == 0}
    }

    // 전체 넓이 - 0의 개수 == 붙여진 스티커 개수
    print(N * M - emptyCnt)
}