백준 18808 스티커 붙이기 Kotlin (시뮬레이션)

문제 출처 : https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

문제

혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다.

반면 아래는 올바르지 않은 모눈종이의 예시이다. 첫 번째는 윗쪽에 불필요한 행이 있고, 두 번째는 왼쪽에 불필요한 열이 있다. 그리고 세 번째는 스티커의 각 칸이 상하좌우로 모두 연결되어 있지 않다.

혜윤이는 자신의 노트북에 이 스티커들을 붙이기로 했다. 혜윤이의 노트북은 마침 직사각형 모양이고, 스티커가 인쇄된 모눈종이와 같은 간격으로 격자가 그려져 있다. 혜윤이는 스티커들을 먼저 받았던 것부터 차례대로 격자에 맞춰서 붙이려고 한다.

혜윤이가 스티커를 붙이는 방법은 다음과 같다.

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

아래의 예시를 통해 스티커를 붙이는 과정을 이해해보자. 노트북은 세로 5칸, 가로 4칸 크기이고, 혜윤이가 가지고 있는 스티커들은 아래와 같다. 왼쪽에서 오른쪽 순으로 스티커를 붙일 것이다.

1. 첫 번째 스티커는 회전 없이 온전히 붙일 수 있는 공간이 아래와 같이 6곳이 있다.이 중에서 가장 위쪽의 위치, 가능한 가장 위쪽의 위치가 여러 개이면 그 중에서 가장 왼쪽의 위치는 첫 번째이다. 스티커를 붙인 후 노트북의 모양은 아래와 같다.
2. 
3. 
4. 두 번째 스티커는 회전 없이 온전히 붙일 수 있는 공간이 없다. 그러나 시계 방향으로 90도 회전한 후에는 붙일 수 있는 공간이 1개 생긴다. 해당 공간에 스티커를 붙인 후 노트북의 모양은 아래와 같다.
5. 
6. 세 번째 스티커는 스티커를 시계방향으로 0, 90, 180, 270도 회전시킨 모양에 대해 전부 확인을 해도 스티커를 붙일 수 있는 공간이 없다. 그러므로 해당 스티커를 붙이지 않고 버린다.
7. 네 번째 스티커는 스티커를 시계방향으로 0, 90, 180도 회전 시킨 모양에 대해 온전히 붙일 수 있는 공간이 없다. 그러나 시계 방향으로 270도 회전한 후에는 공간이 1개 생긴다. 스티커를 붙인 후 노트북의 모양은 아래와 같다. 최종적으로 노트북의 18칸이 스티커로 채워졌다.
8. 

혜윤이는 스티커를 다 붙인 후의 노트북의 모습이 궁금해졌다. 노트북의 크기와 스티커들이 주어졌을 때 스티커들을 차례대로 붙이고 난 후 노트북에서 몇 개의 칸이 채워졌는지 구해보자.

입력

첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 ≤ M ≤ 40), 그리고 스티커의 개수 K(1 ≤ K ≤ 100)이 한 칸의 빈칸을 사이에 두고 주어진다.

그 다음 줄부터는 K개의 스티커들에 대한 정보가 주어진다. 각 스티커는 아래와 같은 형식으로 주어진다.

먼저 i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 Ri(1 ≤ Ri ≤ 10)와 Ci(1 ≤ Ci ≤ 10)가 한 칸의 빈칸을 사이에 두고 주어진다.

다음 Ri개의 줄에는 각 줄마다 모눈종이의 각 행을 나타내는 Ci개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1이다. 0은 스티커가 붙지 않은 칸을, 1은 스티커가 붙은 칸을 의미한다.

문제에서 설명한 것과 같이 스티커는 모두 올바른 모눈종이에 인쇄되어 있다. 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

출력

첫째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력한다.

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 시뮬레이션

풀이

풀다보면 시간이 사라지는 문제.

구현 자체는 그렇게 어려울 것이 없다.

오히려 어렵게 생각해서 dfs로 돌렸다가 스티커 붙일 수 있는지 확인하는 로직이 너무 복잡해져서 다시 생각해봤는데

그냥 인덱스만 잘 다루면 2중 for문으로 해결 가능하다..

 

문제도 길고 코드도 긴 시뮬레이션, 완전 탐색 문제.

풀이는 다음과 같다.

 

1-1. 입력받은 스티커들을 3번 돌린 상태를 저장해놓는다.

(굳이 미리 저장 다 안 해두고, 입력받는 동시에 바로 스티커 붙이는 작업을 하는 것이 더 효율적이고 깔끔할 것 같다.

이것이 가능한 이유는, 한 번 검사한 스티커는 더 이상 찾을 일이 없기 때문이다.)

 

1-2. 스티커들은 10*10 크기의 2차원 그래프에 돌려가며 저장했다. 이 부분은 저마다 인덱스를 편하게 다룰 수 있는 방법으로 하면 된다.

ex) 주어진 입력대로 행과 열의 사이즈가 다른 스티커 그대로 사용, 본인은 스티커 크기가 어쨌든 다 10*10크기로 사용.

 

1-3. 돌리는 로직은 직접 4*4 크기 정도의 배열을 그려보고 이를 90도 뒤집어보면 쉽게 알 수 있다.

 

2. 저장한 모든 스티커들에 대해, 모든 방향에 대해, 2차원 그래프의 왼쪽 위부터 오른쪽 아래까지 스티커를 붙일 수 있는지 확인하고, 붙일 수 있다면 붙인다.

 

3. 붙이는 로직은 검사하는 로직과 동일하다.

(본인은 일단 붙이고 보다가 붙일 수 없게 되는 경우 다시 지워주는 것보다 검사와 붙이기를 분리했다.)

 

4. 노트의 스티커가 붙은 칸들의 개수를 출력한다.

 

하.. 내시간...

 

코드

val br = System.`in`.bufferedReader()

//1<=n,m<=40
//1<=k<=100

lateinit var graph : Array<BooleanArray>
var answer = 0
//스티커 돌리기
fun rotate(sticker : Array<Array<IntArray>>){

    for(dir in 1 .. 3) {
        for (r in sticker[dir].indices) {
            for (c in sticker[dir][r].indices) {
                sticker[dir][r][c] = sticker[dir-1][sticker[dir-1].size-c-1][r]
            }
        }

    }
}

//붙이기
fun attach(i : Int,j : Int,n : Int,m : Int,sticker : Array<IntArray>,visitedSticker : Array<BooleanArray>){
    var cr =-1
    var cc =-1
    for(r in 0 until 10){
        for(c in 0 until 10){
            if(sticker[r][c]==1){
                if(cr==-1){
                    cr=r
                    cc=c
                }
                
                val nr = i+r-cr
                val nc = j+c-cc
                graph[nr][nc]=true
                answer++
            }

        }
    }
}

//붙일 수 있나 확인
fun dfs(i : Int, j : Int, n : Int, m : Int, sticker : Array<IntArray>) : Boolean{
    var cr =-1
    var cc =-1
    for(r in 0 until 10){
        for(c in 0 until 10){
            if(sticker[r][c]==1){
                if(cr==-1){
                    cr=r
                    cc=c
                }
                //넣을 수 있는지 검사
                val nr = i+r-cr
                val nc = j+c-cc
                if(nr !in 0 until n || nc !in 0 until m) return false
                if(graph[nr][nc]) return false
            }

        }
    }
    return true
}

fun main() = with(System.out.bufferedWriter()){

    val (n,m,k) = br.readLine().split(' ').map{it.toInt()}
    graph = Array(n){BooleanArray(m)}
    val sticker = Array(k){ Array(4){ Array(10) { IntArray(10) } } }


    for(i in 0 until k){
        val (r, c) = br.readLine().split(' ').map{it.toInt()}
        for(j in 0 until r){
            var idx = 0
            br.readLine().split(' ').map{
                val num = it.toInt()
                sticker[i][0][j][idx++] = num
            }
        }
        //스티커 원본을 3번 돌린 값들 모두 저장
        rotate(sticker[i])
    }

    for(s in sticker.indices) {
        var canAttach = false
        //스티커 4방향 붙여보기
        for (dir in 0 until 4) {
            //왼쪽 위부터
            for (i in 0 until n) {
                for (j in 0 until m) {
                    //스티커 붙은 칸 스킵
                    if (graph[i][j]) continue

                    canAttach = dfs(
                        i,
                        j,
                        n,
                        m,
                        sticker[s][dir])
                    //붙일 수 있으면 붙이고 사용 처리
                    if (canAttach) {
                        attach(
                            i,
                            j,
                            n,
                            m,
                            sticker[s][dir],
                            Array(sticker[s][dir].size) { BooleanArray(sticker[s][dir][0].size) })
                        break
                    }
                    if (canAttach) break
                }
                if (canAttach) break
            }
            if(canAttach) break
        }
    }
    write("$answer")
    close()
}