백준 21277 짠돌이 호석 Kotlin (완전탐색)

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

21277번: 짠돌이 호석

문제

DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태로 이루어져 있다. 각 격자는 정사각형 모양이며, 퍼즐 조각이 있을 수도 있고, 없을 수도 있다. 즉, 아래 그림도 올바른 퍼즐의 완성 형태이다.

성공적으로 DIY가 끝나서 퍼즐이 2개가 완성되었는데, 보관해야 하는 액자를 아직 구매하지 않았다. 그 이유는, 호석이는 엄청난 짠돌이기 때문에 퍼즐 하나마다 액자 하나를 사는 것은 상상도 못하기 때문이다. 액자의 가격은 액자의 넓이(행의 개수 × 열의 개수) 로 결정된다. 즉, 퍼즐 두 개를 퍼즐 조각끼리 같은 격자에서 만나지 않도록 배치해서 하나의 액자에 담는 방법 중에 가장 적은 비용일 때를 찾아보자! 단, 각 퍼즐은 90도, 180도, 270도로 자유롭게 회전시켜도 된다.

입력

첫 줄에 퍼즐의 크기를 나타내는 N1, M1이 공백으로 구분되어 주어진다. 이어서 N1개의 줄에 걸쳐서 완성된 첫 번째 퍼즐의 정보가 주어진다. 각 행마다 M1개의 0 또는 1이 공백없이 주어진다. 다음 줄에 퍼즐의 크기를 나타내는 N2, M2이 공백으로 구분되어 주어진다. 이어서 N2개의 줄에 걸쳐서 완성된 두 번째 퍼즐의 정보가 주어진다. 각 행마다 M2개의 0 또는 1이 공백없이 주어진다. 0이 써있는 격자는 퍼즐 조각이 없는 격자이며 1은 있는 격자이다. 두 퍼즐 모두 4개 모서리에 최소 하나의 1은 존재하는 것이 보장된다.

출력

두 개의 퍼즐을 담을 수 있는 액자들 중에 최소 넓이를 출력한다.

제한

• 1 ≤ N1, M1, N2, M2 ≤ 50

알고리즘 분류

• 구현
• 브루트포스 알고리즘

 

풀이

지금보니 저 퍼즐 생선 눈알이 좀 무섭네

코테에서 종종 보이는 유형이다.

코테에서도 봤고 프로그래머스에서 풀었던 유형 같은데 기억이 안 난다. 아시는 분 있으면 제보 좀 해주세요!

그냥 완전 탐색을 말하는 게 아니라, 두 개의 그래프를 비교하는 유형을 말하는 것이다.

결론부터 말하면 풀이는 다음과 같다.

 

1. 두 퍼즐을 비교하기 위해 큰 그래프를 하나 둔다고 생각한다.

2-1. 하나의 퍼즐을 전체 그래프 상에 고정한다.

2-2. 이때 퍼즐의 최대 크기는 50*50으로, 고정할 퍼즐을 가운데에 둔다고 생각하면 전체 그래프의 크기는 150*150 이상이어야 한다.

3. 나머지 퍼즐을 4방향으로 미리 저장해둔다.(rotate함수를 만들어서 매번 90도씩 돌려도 된다. 본인은 그냥 4방향 저장해놨다.)

4. 나머지 한 퍼즐만 한 칸씩 이동하면서 4방향 모두 비교한다.

5. 비교했을 때 두 퍼즐이 겹친다면 쓰레기값을 리턴하고, 겹치지 않는다면 두 퍼즐을 합친 크기를 리턴하여 최소 크기를 갱신한다.

 

풀이는 이 정도고, 큰 그래프를 하나 두고 퍼즐 하나를 고정, 나머지 한 퍼즐을 한 칸씩 이동한다는 것이 조금 이해하기 어려울 수 있다.

그림으로 살펴보자.

키노트로 열심히 만들었다.

사이즈가 정확하진 않지만 이해하기엔 문제 없다.

초록색 네모가 고정된 퍼즐이고, 흰색 네모가 나머지 퍼즐이다.

전체 그래프 150*150에서 고정 퍼즐은 가운데 50,50에 고정하고, 나머지 퍼즐을 0,0부터 시작해서 100,100까지
4방향으로 돌려가며 비교하면 된다. 그러면 두 퍼즐을 모든 형태로 붙여볼 수 있고, 겹치지 않게 옆에 붙인 경우도 계산된다.

 

rotate() 함수로 매번 돌리면 코드는 편하지만 리소스를 잡아먹을 것 같으니 4방향을 첨부터 저장하고 쓰는 게 더 좋을 것 같다.

주의할 점은 두 퍼즐을 합친 결과의 넓이를 구할 때 회전한 퍼즐의 n,m값이 바뀌는 것 정도가 있다.

코드

val br = System.`in`.bufferedReader()
fun getIntGraph() = br.readLine().split(' ').map { it.toInt() }

val puzzle1 = Array(150) { IntArray(150) }
lateinit var puzzle2: Array<Array<IntArray>>
var answer = Int.MAX_VALUE
fun simulation(i: Int, j: Int, n1: Int, m1: Int, pzl2: Array<IntArray>): Int {
    //i==0~100
    //j==0~100
    val n2 = pzl2.size
    val m2 = pzl2[0].size
    for (r in pzl2.indices) {
        for (c in pzl2[r].indices) {
            //겹치면 리턴
            if (puzzle1[i + r][j + c] and pzl2[r][c] == 1) return Int.MAX_VALUE
        }
    }
    //안 겹치면 계산
    val minR = i.coerceAtMost(50)
    val maxR = (50+n1).coerceAtLeast(i+n2)
    val minC = j.coerceAtMost(50)
    val maxC = (50+m1).coerceAtLeast(j+m2)
    return (maxR-minR)*(maxC-minC)
}

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

    //input
    val (n1, m1) = getIntGraph()
    for (i in 0 until n1) {
        val line = br.readLine()
        for (j in 0 until m1) {
            puzzle1[50 + i][50 + j] = Character.getNumericValue(line[j])
        }
    }
    val (n2, m2) = getIntGraph()
    val temp = Array(n2) {
        val line = br.readLine()
        IntArray(m2) {
            Character.getNumericValue(line[it])
        }
    }

    //5,3
    puzzle2 = Array(4) {
        when (it) {
            0 -> {
                Array(n2) { r ->
                    IntArray(m2) { c ->
                        temp[r][c]
                    }
                }
            }
            1 -> {
                Array(m2) { r ->
                    IntArray(n2) { c ->
                        temp[n2 - c - 1][r]
                    }
                }
            }
            2 -> {
                Array(n2) { r ->
                    IntArray(m2) { c ->
                        temp[n2 - r - 1][m2-c-1]
                    }
                }
            }
            else -> {
                Array(m2) { r ->
                    IntArray(n2) { c ->
                        temp[c][m2 - r - 1]
                    }
                }
            }
        }
    }

    //solve
    for (r in 0..100) {
        for (c in 0..100) {
            for(i in 0 until 4) {
                answer = answer.coerceAtMost(simulation(r, c, n1, m1,puzzle2[i]))
            }
        }
    }

    //output
    write("$answer")
    close()
}