[Kotlin] 백준 1018번 : 체스판 다시 칠하기 <Silver 4>

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

Code

---

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min

val ANSWER = mutableListOf<List<Char>>(
    listOf('W','B', 'W', 'B', 'W','B', 'W', 'B'),
    listOf('B', 'W', 'B', 'W','B', 'W', 'B', 'W'),
    listOf('W','B', 'W', 'B', 'W','B', 'W', 'B'),
    listOf('B', 'W', 'B', 'W','B', 'W', 'B', 'W'),
    listOf('W','B', 'W', 'B', 'W','B', 'W', 'B'),
    listOf('B', 'W', 'B', 'W','B', 'W', 'B', 'W'),
    listOf('W','B', 'W', 'B', 'W','B', 'W', 'B'),
    listOf('B', 'W', 'B', 'W','B', 'W', 'B', 'W')
)

val SIZE = 8

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val (M, N) = readLine().split(" ").map { it.toInt() } // M과 N 입력

    val input = mutableListOf<List<Char>>()
    var result = Int.MAX_VALUE

    repeat(M){
        val line = readLine().map { it.toChar() }

        input.add(line)
    }

    for (i in 0 .. M - SIZE){
        for (j in 0 .. N - SIZE){
            result = min(getCount(i,j,input), result)
        }
    }

    println(result)
}

fun getCount(i: Int, j: Int, input: MutableList<List<Char>>): Int{
    var result = 0

    repeat(SIZE){ x->
        repeat(SIZE){ y->
            if (ANSWER[x][y] != input[i+x][j+y]) result++
        }
    }

    return min(result, SIZE * SIZE - result)
}

---

정말 정석적인 방법으로 문제를 풀었다.

시간을 들인다면 더 효율적인 알고리즘을 작성할 수 있었겠지만, 빠르게 작성할 수 있는 알고리즘을 적용한 근거가 있다.

 

첫 번째. 브루트포스 알고리즘이 사용 가능한 범위

N과 M의 값은 최대 50까지이다. 그렇기 때문에 과하게 많지는 않은 경우의 수가 나오기 때문에 브루트포스를 사용했다.

 

두 번째. 시간 절약

아닌 사람이 있을 수도 있지만, 나는 알고리즘을 공부하는 이유가 코딩테스트 때문이다.

코딩테스트때는 한문제만 나오고 끝이 아니라 여러 문제가 나온다. 그렇기 때문에 앞에 문제에서 시간을 최소한으로 사용하고 뒷부분 문제를 푸는 것이 중요하다. 그렇기 때문에 이렇게 로직이 바로 생각나는 문제의 경우 일단 생각난대로 풀고, 뒤에 문제를 다 푼 후 시간이 날때 돌아와서 리펙토링 하는 것이 더 좋다고 생각한다.

 

 

 

여튼, 사담이 길었다.

문제관련으로 돌아가자면 이 문제는 8X8짜리 체스판을 만드는 문제다.

입력 받는 칸이 그냥 넓게 주어지니까 그 중에서 가장 적게 바꿔도 되는, 다시 말하면 가장 정상적인 체스판을 찾고 완벽하게 만드는데 바꿔야 하는 값의 수를 구하는 문제다.

 

그래서 난 브루트포스를 사용해서 전부 다 확인하자는 생각을 했다.

입력 받은 칸에서 왼쪽 위에서 시작하여 한칸씩 오른쪽, 한칸씩 아래쪽으로 이동하며 모든 8X8 체스판의 우측 상단 위치를 찾았고, 그 값을 활용하여 함수로 해당 체스판 내부의 값을 확인했다.

 

 

확인과정에서 난 ANSWER라는 정상적인 체스판을 만들었다. 이 판은 좌측 상단이 흰색인 체스판이다.

이 판을 이용하여 입력받은 값과 비교를 진행 후 다시 칠해야 하는 정사각형의 개수의 최솟값을 구했다.

 

이 때 왼쪽 위가 흰색인 체스만 사용하여 나온 값을 64에 빼서 왼쪽 위가 검정인 체스판일 때의 경우를 구했다.

그래서 두 값 중 작은 값을 return 하여 더 작은 결과를 구하고자 했다.

 

 

함수에서 값을 리턴 받은 후 기존 값과 비교하여 더 작은 값을 유지하는 방식으로 문제를 풀었다.

 

 

 

 

답지를 하드코딩해두고, SIZE를 하드코딩 해둔 것을 별로 안좋게 보는 사람들이 있을 것이다. 나 또한 예전에는 그랬고.

근데 얼마전 공부를 하며 느낀 것은 코딩테스트는 코딩테스트고 개발은 개발이다. 각 분야에서 최고의 효율을 추구하면 되는 것이고, 다른 분야의 기준을 가져다 대면 안된다는 생각이 들었다.

코딩테스트 문제를 풀면서 진행시키지도 않을 확장성을 고려하고 예쁜 코드를 추구하는 것 보다 빠르고 효율적인 코드를 만드는 것이 더 좋다고 본다.