문제 풀이
브루트 포스, 비트 마스킹
clicks = 각 칸이 눌릴 때 색이 바뀌는 칸을 비트 마스킹 해놓은 것
res = 입력으로 주어지는 최종적으로 바뀌어야 하는 보드의 상태를 비트 마스킹 해놓은 것
board = 모든 칸이 흰색인 처음 보드 상태
bitCount = 현재 클릭을 하는 칸의 갯수
모든 칸이 흰색인 보드 상태에서 최소한의 클릭 횟수로 입력으로 주어진 보드 상태로 만들어야 함
칸을 한번 누르면 인접한 상하 좌우 칸까지 색이 바뀌는데 2번 누르면 원래 상태로 돌아옴
따라서 칸을 누르거나 누르지 않거나 2가지 상태로 나뉘기 때문에 모든 경우의 수가 512개로 충분히 할만 함
칸이 2가지 색으로 나뉘고 칸을 누르는지 마는지 여부도 2가지 상태로 나뉠 때 총 9칸이므로 비트 마스킹으로 처리 가능
각 칸마다 눌리면 어떤 칸이 색이 바뀌는지를 clicks에 미리 저장해놓음
입력으로 목표 보드가 어떤 형태로 나오는지 주어지면 res에 그 보드의 상태를 비트 마스킹으로 저장함
저장하면 보드의 첫 상태를 board에 0으로 초기화하고 각 칸을 누르는지 마는지를 비트마스킹으로 표현하면 0부터 512 미만의 숫자로 나오므로 이를 i로 나타냄
i마다 어떤 칸을 누르는지 알아봐야 하므로 이진수로 각 자리마다 1이 있는지를 bitCount에 저장하고 1이 있다면 그 칸을 누른 것이므로 clicks 배열에서 해당 칸이 눌렸을 때의 비트 마스킹을 빼와서 board와 xor 연산을 해 색이 바뀌는 칸들의 비트를 반전시킴
모든 i에 대해서 반복하는 도중 목표 보드 상태인 res와 board가 같아지면 최소 횟수가 bitCount가 되므로 bitCount를 출력해주면 정답
풀이 설명
당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색에서 흰색으로, 혹은 흰색에서 검은색으로 변할 것이다.
당신은 모든 칸이 흰색인 3x3 보드를 입력으로 주어지는 보드의 형태로 바꾸려고 한다. 보드를 회전시킬수는 없다.
같은 칸을 2번 클릭하면 원래 상태로 들어오기 때문에 한 칸마다 클릭하거나 클릭하지 않는다는 선택지만 있다. 칸이 총 9칸 있기 때문에 모든 경우의 수가 512개로 모든 경우의 수를 확인해도 된다.
그러나 9칸이 현재 흰색인지 검은색인지를 나타내야 하는데 이를 매번 배열로 만들게 된다면 메모리가 너무 많이 낭비될 수 있다. 총 9칸이고 칸마다 상태가 2가지밖에 없으므로 비트 마스킹으로 나타낼 수 있다.
또한 어떤 칸을 클릭할지 아닐지도 9칸을 2가지 상태로 나타낼 수 있으므로 이도 똑같이 비트 마스킹으로 나타낼 수 있다.
이에 따라 보드의 각 칸을 나타낼 때 9칸의 비트를 맨 윗줄의 행부터 맨 아랫줄의 행까지로 나타낸다. 그 이후에 각 칸을 눌렀을 때 색이 바뀌어야 하는 칸은 정해져있으므로 미리 clicks 배열에 어떤 칸이 바뀌어야 하는지를 비트 마스킹으로 저장해준다.
이후에 매번 바뀌어야하는 보드가 입력으로 주어지면 해당 보드를 비트 마스킹으로 나타내 res에 저장해준다. 이때 검은색 칸을 1로 나타낸다.
그 이후에는 맨 처음에 모든 칸이 흰색인 보드에서 바뀐다고 했으므로 첫 보드 상태를 board에 저장해야 하므로 0으로 초기화를 해준다.
그 이후 9칸에 대해 누르는지 마는지 2가지 상태로 나타난다고 했으므로 이를 비트마스킹으로 나타내면 0부터 2의 9승인 512 미만의 숫자로 나타나게 된다. 이에 따라 0부터 512 미만까지의 숫자를 i로 나타낸다.
그 이후 이 i는 어떤 칸이 눌려야 하는지 정보가 비트 마스킹 되어있으므로 어떤 칸이 눌려야 하는지 변환해서 알아보아야 한다. 이에 따라 i와 1부터 한자리씩 and 연산을 해보며 어떤 칸이 눌려야 하는지를 알아본다.
각 칸마다 눌려야 한다면 1인 비트의 갯수 bitCount를 1씩 증가시키고 해당 칸을 눌렀을 때 색이 바뀌어야 하는 칸을 clicks 배열에서 가져와 board와 xor 연산을 통해 해당 칸을 눌렀을 때 색이 바뀌는 것을 보드에 구현해준다.
여기서 bitCount가 각 칸을 누르는 횟수가 되므로 board가 res와 같아지는 i를 찾게 되면 이 값이 칸을 누르는 최소 횟수가 되게 된다. 따라서 매 입력마다 bitCount를 출력해주면 정답이 된다.
소스 코드
fun main() = System.`in`.bufferedReader().run {
val P = readLine().toInt()
val sb = StringBuilder()
val clicks = intArrayOf(
0b110100000,
0b111010000,
0b011001000,
0b100110100,
0b010111010,
0b001011001,
0b000100110,
0b000010111,
0b000001011
)
for(t in 0 until P){
var res = 0
for(i in 0 until 3){
val s = readLine()
for(j in 0 until 3){
if(s[j] == '*') res = res or 1
res = res shl 1
}
}
res = res shr 1
for(i in 0 until 512){
var board = 0
var bitCount = 0
for(j in 0 until 9){
if((1 shl j) and i != 0){
bitCount++
board = board xor clicks[j]
}
}
if(board == res){
sb.append(bitCount).append("\n")
break
}
}
}
print(sb)
}