[백준] 3085번 사탕 게임(브루트 포스 - 완전탐색)[Kotlin - 코틀린]

백준 3085번 문제입니다. (solved.ac) 기준 실버 3 문제입니다.

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

3085번: 사탕 게임

문제

문제 접근

완전 탐색으로 접근하였습니다.

제가 짠 코드는 대략 4중 포문인데 n의 범위가 50이므로 50^4 => 6250000입니다. 시간 제한인 1초 안에는 10^8(10억)번의 연산을 할 수 있으므로 시간 복잡도에는 문제가 생기지 않을 것이라고 판단하고 그대로 진행했습니다.

코드는 길지만 로직은 간단합니다.

보드의 정보를 입력받고 보드를 완전탐색하며 우측에 있는 사탕, 하단에 있는 사탕과 모양이 다르다면 위치를 바꾸고 바꾼 위치를 기준으로 먹을 수 있는 최대 사탕의 개수를 구해준 후 다시 보드를 원래대로 돌려놓습니다. 이 과정을 보드의 모든 인덱스에 접근하며 반복합니다.

정답 코드

fun main() {

    val n = readln().toInt()
    val board = mutableListOf<MutableList<Char>>()

    var canEatMax = 0
    // 보드에 정보를 입력받는 과정
    repeat(n) {
        val row = readln().toMutableList()
        board.add(row)
    }

    // 완전 탐색을 진행
    for (i in 0 until n) {
        for (j in 0 until n) {

            // 현재 좌표의 사탕 모양
            val curChar = board[i][j]

            // 범위 내에서만
            if (i + 1 < n) {
                val belowChar = board[i + 1][j]
                // 아래와 다를 때
                if (curChar != belowChar) {
                    // 사탕 위치 바꾸기
                    board[i][j] = belowChar
                    board[i + 1][j] = curChar
                    // 바꾼 상태에서 먹을 수 있는 최대 사탕의 개수 확인
                    var canEatCnt = checkCanEatCnt(board)
                    if (canEatMax < canEatCnt) canEatMax = canEatCnt
                    // 사탕 위치 복구
                    board[i][j] = curChar
                    board[i + 1][j] = belowChar

                }
            }

            // 범위 내에서만
            if (j + 1 < n) {
                val rightChar = board[i][j + 1]
                // 우측과 다를 때
                if (curChar != rightChar) {
                    // 사탕 위치 바꾸기
                    board[i][j] = rightChar
                    board[i][j + 1] = curChar
                    // 바꾼 상태에서 먹을 수 있는 최대 사탕의 개수 확인
                    var canEatCnt = checkCanEatCnt(board)
                    if (canEatMax < canEatCnt) canEatMax = canEatCnt
                    // 사탕 위치 복구
                    board[i][j] = curChar
                    board[i][j + 1] = rightChar
                }
            }

        }
    }

    print(canEatMax)

}

// 현재 보드모양을 기준으로 먹을 수 있는 사탕의 최대 개수를 반환하는 함수
fun checkCanEatCnt(board: MutableList<MutableList<Char>>): Int {

    var maxCnt = 0

    // 행
    for (i in 0 until board.size) {
        // 연속된 사탕의 수(먹을 수 있는 사탕의 수)
        var curRowCnt = 1
        // 연속되고있는 문자
        var lastChar = board[i][0]
        for (j in 1 until board.size) {
            var curChar = board[i][j]

            // 현재 단어와 이전 단어가 같다면
            if (lastChar == curChar) {
                curRowCnt++
            } else {
                lastChar = curChar
                if (maxCnt < curRowCnt) maxCnt = curRowCnt
                curRowCnt = 1
            }
        }
        if (maxCnt < curRowCnt) maxCnt = curRowCnt
        curRowCnt = 1

    }

    // 열
    for (i in 0 until board.size) {
        // 연속된 사탕의 수(먹을 수 있는 사탕의 수)
        var curColCnt = 1
        // 연속되고있는 문자
        var lastChar = board[0][i]
        for (j in 1 until board.size) {
            var curChar = board[j][i]

            // 현재 단어와 이전 단어가 같다면
            if (lastChar == curChar) {
                curColCnt++
            } else {
                lastChar = curChar
                if (maxCnt < curColCnt) maxCnt = curColCnt
                curColCnt = 1
            }
        }
        if (maxCnt < curColCnt) maxCnt = curColCnt
        curColCnt = 1

    }

    return maxCnt
}