Today I Learned

오늘은 코테를 코틀린으로 공부했다.

색종이 만들기

백준 2630번 https://www.acmicpc.net/problem/2630

문제

여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 그림의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

입력 예시
8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
출력 예시
9
7

풀이과정

• 큰걸 분할해서 작은걸로 만들고 계속 파고들어야되는 구조이므로 재귀를 통해 문제를 해결했다.
  재귀적으로 돌아가는 함수를 메인 함수 외에 하나 더 만들고, 간단하게 결과를 받기 위해 데이터 클래스를 하나 만들어주면서 구성했다.

1. 메인함수
   n의 정보를 받고, 종이의 정보도 받아 2차원 배열에 저장해둔다.
   cutPaper 함수를 호출해 결과값을 받아 출력한다.

2. 코틀린에서는 클래스를 간단하게 만들 수 있다. 이를 이용해 결과를 받을 클래스를 아주 간단하게 data class와 프로퍼티를 이용해 단 한줄로 만들어 사용한다. 이 클래스에서는 흰색과 파란색 종이의 개수를 담는다.

3. cutPaper 함수
   입력으로 종이 정보 배열과 시작위치(x,y), 종이의 크기를 받고 Result 클래스로 결과를 출력해준다. 시작위치부터 종이를 탐색하면서 같은 색상인지 확인하면서 변수에다 카운트를 한다.
   만약 다른 색상이 있으면 종이를 더 작은 사이즈로 나눠 재귀적으로 호출해 각 부분을 다시 확인한다. 만약 모든 부분이 같은 색이라면 해당 부분의 색상을 카운트해 return 한다.

Kotlin 코드

fun main() {
    val n = readln().toInt()
    val paper = Array(n) { IntArray(n) }

    for (i in 0 until n) {
        val arr = readln().split(" ").map { it.toInt() }
        for (j in 0 until n) {
            paper[i][j] = arr[j]
        }
    }

    val result = cutPaper(paper, 0, 0, n)
    println(result.white)
    println(result.blue)

}

data class Result(val white: Int, val blue: Int)

fun cutPaper(paper: Array<IntArray>, x: Int, y: Int, size: Int): Result {
    val color = paper[x][y]
    var whiteCount = 0
    var blueCount = 0

    for (i in x until x + size) {
        for (j in y until y + size) {
            if (paper[i][j] != color) {
                val halfSize = size / 2
                val topLeft = cutPaper(paper, x, y, halfSize)
                val topRight = cutPaper(paper, x, y + halfSize, halfSize)
                val bottomLeft = cutPaper(paper, x + halfSize, y, halfSize)
                val bottomRight = cutPaper(paper, x + halfSize, y + halfSize, halfSize)
                return Result(
                    white = topLeft.white + topRight.white + bottomLeft.white + bottomRight.white,
                    blue = topLeft.blue + topRight.blue + bottomLeft.blue + bottomRight.blue
                )
            }
        }
    }

    if (color == 0) whiteCount++ else blueCount++
    return Result(whiteCount, blueCount)
}