[백준/BOJ] 3085번: 사탕 게임

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

3085번: 사탕 게임

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

해설

처음 보드를 사탕으로 채웠을 때 최대의 값으로 연속된 사탕의 개수를 알아낸다.

다음부턴 반복문을 돌리며 이번 칸과 다음 칸의 사탕의 색이 다르다면 둘의 위치를 바꿔 연속된 사탕의 개수를 세어준다.

칸을 바꾸고 사탕을 세었다면 보드를 원래대로 되돌려 놓는다.

 

칸을 가로로 바꿀 함수, 세로로 바꿀 함수, 가로로 연속된 사탕의 수를 셀 함수, 세로로 연속된 사탕의 수를 셀 함수를 만들었다.

 

칸을 바꾸고 사탕의 수를 세어 미리 선언해둔 max 변수에 더 큰 값을 저장해준다.

소스 코드

lateinit var board: Array<CharArray>
var n = 0
var max = 0

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    board = Array(n) { CharArray(n) { '.' } }
    repeat(n) { i ->
        val candy = readLine()
        repeat(n) { j ->
            board[i][j] = candy[j]
        }
    }
    rowSearch()
    colSearch()
    repeat(n) { i ->
        repeat(n - 1) { j ->
            if(board[i][j] != board[i][j+1]) {
                rowSwap(i, j)
                rowSearch()
                colSearch()
                rowSwap(i, j)
            }
            if(board[j][i] != board[j+1][i]) {
                colSwap(j, i)
                rowSearch()
                colSearch()
                colSwap(j, i)
            }
        }
    }
    println(max)
}

fun rowSwap(y: Int, x: Int) {
    val temp = board[y][x]
    board[y][x] = board[y][x+1]
    board[y][x+1] = temp
}

fun colSwap(y: Int, x: Int) {
    val temp = board[y][x]
    board[y][x] = board[y+1][x]
    board[y+1][x] = temp
}

fun rowSearch() {
    var cnt = 0
    for(i in 0 until n) {
        var standard = board[i][0]
        for(j in 0 until n) {
            if(board[i][j] == standard) cnt++
            else {
                max = maxOf(max, cnt)
                standard = board[i][j]
                cnt = 1
            }
        }
        max = maxOf(max, cnt)
        cnt = 0
    }
}

fun colSearch() {
    var cnt = 0
    for(i in 0 until n) {
        var standard = board[0][i]
        for (j in 0 until n) {
            if (board[j][i] == standard) cnt++
            else {
                max = maxOf(max, cnt)
                standard = board[j][i]
                cnt = 1
            }
        }
        max = maxOf(max, cnt)
        cnt = 0
    }
}