백준 3085 사탕 게임 Kotlin (완전 탐색)

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

3085번: 사탕 게임

문제

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

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

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

입력

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

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

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

출력

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

힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

알고리즘 분류

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

풀이

완전 탐색 문제이다!

본인이 그래프 탐색을 꼼꼼히 한다면 어렵지 않게 풀 수 있다.

풀이는 다음과 같다.

 

1. 그래프에서 서로 swap해줄 두 칸(a,b)을 정하고 swap한다.

2. swap할 칸의 기준이 되는 a를 방문 처리한다.

3. swap한 그래프에서 2중 포문으로 가로, 세로로 연속된 사탕의 최댓값을 갱신한다.

4. swap 했던 그래프를 다시 원상복귀한다.

5. 그래프의 남은 기준점 a에 대해 2~4를 반복한다. 이때 b가 방문 처리되는 경우는
a->b 스왑을 b->a스왑으로 또 하는 경우이므로 스킵하면 된다.

 

특별한 알고리즘이 필요하진 않고 최댓값 구하기 구현하는 부분, swap하는 부분만 신경 쓰면 된다.

본인은 방문 처리를 했지만, 방문 처리를 하지 않아도 이 문제에선 재방문하는 경우가 많지 않아서 시간 차이가 크게 나지 않는다. 그냥 말 그대로 완전! 탐색해서 빠르게 풀고 넘어가자.

 

 

 

코드

val br = System.`in`.bufferedReader()
val dirXY : Array<IntArray> = arrayOf(intArrayOf(0,1),intArrayOf(1,0),intArrayOf(-1,0),intArrayOf(0,-1))

//1<=n<=50
var answer =0
var max=0
lateinit var graph : Array<CharArray>

fun findMax(n : Int){
    for(r in 0 until n){
        var curC = graph[r][0]
        var cCnt = 0
        var curR = graph[0][r]
        var rCnt = 0
        for(c in 0 until n){
            //가로 탐색
            if(curC==graph[r][c]){
                cCnt++
                max = max.coerceAtLeast(cCnt)
            }
            else{
                curC=graph[r][c]
                cCnt=1
            }
            //세로 탐색
            if(curR==graph[c][r]){
                rCnt++
                max = max.coerceAtLeast(rCnt)
            }
            else{
                curR = graph[c][r]
                rCnt=1
            }
        }
    }
}

fun choiceSwap(n : Int, r: Int, c : Int){

    for(dir in 0 until 4){
        val nr = r + dirXY[dir][0]
        val nc = c + dirXY[dir][1]
        if(nr !in 0 until n || nc !in 0 until n) continue
        if(graph[r][c] == graph[nr][nc]) continue

        graph[r][c] = graph[nr][nc].also{graph[nr][nc] = graph[r][c]}
        findMax(n)
        answer= answer.coerceAtLeast(max)
        max = 0
        graph[r][c] = graph[nr][nc].also{graph[nr][nc] = graph[r][c]}
    }

}


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

    val n = br.readLine().toInt()
    graph = Array(n){br.readLine().toCharArray()}

    findMax(n)
    answer= answer.coerceAtLeast(max)
    max = 0

    for(i in 0 until n){
        for(j in 0 until n){
            choiceSwap(n,i,j)
        }
    }

    write("$answer")

    close()
}