백준 10472 십자뒤집기 Kotlin (bfs, 비트마스킹)

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

10472번: 십자뒤집기

문제

당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색에서 흰색으로, 혹은 흰색에서 검은색으로 변할 것이다.

당신은 모든 칸이 흰색인 3x3 보드를 입력으로 주어지는 보드의 형태로 바꾸려고 한다. 보드를 회전시킬수는 없다.

Figure D.1: 예제 입력

입력

첫 줄에는 테스트 케이스의 숫자 P(0 < P ≤ 50)이 주어진다.

각각의 테스트 케이스에 대해서 세 줄에 걸쳐 한 줄에 세 글자씩이 입력으로 들어온다. "*"은 검은색을 뜻하며 "."은 흰색을 뜻한다.

출력

각각의 테스트 케이스에 대해서 흰 보드를 입력에 주어진 보드로 바꾸는 데 필요한 최소 클릭의 횟수를 구하여라.

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색

풀이

두 가지 풀이가 가능할 것 같다.

bfs로 모든 경우를 탐색하는 것은 같고, 방문한 상태를 체크하는 것은 

CharArray + set으로 할 수 있고,

비트 마스킹을 이용할 수 있다.

본인은 비트 마스킹을 이용했다.

 

일단 접근 방법은 흰 보드에서 주어진 보드 상태를 만드는 데 걸린 횟수,

주어진 보드 상태에서 흰 보드를 만드는 데 걸린 횟수 둘 중 하나로 풀면 된다.

본인은 주어진 보드 상태에서 흰 보드를 만드는 횟수를 구했다.

생각해보니 흰 보드에서 주어진 보드 상태를 만드는 것이 더 깔끔할 것 같다.

 

키 포인트는 다음과 같다.

문제에서 주어진

*..

**.

*..

그래프를 보자.

이를 1차원으로 펼치면

*..**.*..이고,

이를 비트로 표현하면 100110100(2)이다.

또 이를 int형으로 표시하면 308이다.

즉 나올 수 있는 값은 최대 111111111(2)이기 때문에 visited 배열을 [(1 << 9) -1]로 설정하면 모든 그래프 상태를

체크할 수 있다.

이후 그래프의 상태별로 그래프의 모든 칸에 대해 인접 4방향을 xor 연산을 해가며 nextState를 구해보고,

nextState가 0이 되는 순간 (000000000(2)) 주어진 그래프를 흰 그래프로 만든 순간이므로 횟수를 반환하고 종료한다.

 

코드

import java.util.*

val br = System.`in`.bufferedReader()

val dirXY = arrayOf(arrayOf(-1, 0), arrayOf(0, 1), arrayOf(1, 0), arrayOf(0,-1))

fun bfs(state : Int, visited : BooleanArray) : Int{

    val q : Queue<Pair<Int,Int>> = LinkedList()
    q.add(Pair(state,0))
    visited[state]=true
    if(state==0){
        return 0
    }

    while(q.isNotEmpty()) {
        val (curState,cnt) = q.poll()
        for (i in 8 downTo 0) {
            val cr = i/3
            val cc = i%3
            var nextState = curState xor (1 shl (8-i))
            for(j in 0 until 4){
                val nr = cr + dirXY[j][0]
                val nc = cc + dirXY[j][1]
                if(nr !in 0 until 3 || nc !in 0 until 3) continue
                val idx = 8-(nr*3 + nc)
                nextState = nextState xor (1 shl idx)
            }
            if(nextState==0){
                return cnt+1
            }
            if(visited[nextState])continue
            visited[nextState]=true
            q.add(Pair(nextState,cnt+1))
        }
    }
    return -1
}

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

    val t = br.readLine().toInt()

    repeat(t){
        val graph = Array(3){br.readLine()}
        var state=0
        for(i in 0 until 9){
            val r = i/3
            val c = i%3
            if(graph[r][c]=='*'){
                state += 1 shl (8-i)
            }
        }
        write("${ bfs(state, BooleanArray(1 shl 9)) }\n")
    }

    close()
}