[프로그래머스] 2차원 동전 뒤집기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131703

2차원 공간에서 동전의 앞, 뒷면이 담긴 배열 beginning(사진의 왼쪽)을, 목표하는 2차원 공간에서의 동전의 앞, 뒷면이 담긴 배열 target(사진의 오른쪽)으로 바꾸려고 한다.

동전을 뒤집을 때는 그 동전을 포함한 열 혹은 행을 한번에 뒤집어야만 한다.

이때, beginning을 target으로 바꿀때, 행과 열을 뒤집은 수의 최솟값을 return하는 문제이다. 단, 목표 상태로 바꿀 수 없는 경우, -1를 return한다.

 

제한사항

target의 배열 크기와 beginning의 배열 크기는 같으며,

가로의 길이와 세로의 길이는 각각 1~10 사이이다.

 

풀이

일단 문제에서 알 수 있는 점을 생각해보았다.

• 뒤집은 행 혹은 열은 2번 이상 돌릴 필요가 없다. (2번 돌리면 정확히 원래의 상태로 돌아간다.)
• 뒤집는 행과 열의 순서는 고려할 필요가 없다.
  • 1번 열 -> 4번 열 -> 2번 행 순서로 뒤집는 것의 결과는 2번 행 -> 1번 열 -> 4번 열 순서로 뒤집는 것과 결과가 같다.
• 총 뒤집는 횟수의 최대값는 가로의 길이 + 세로의 길이 - 1이다. (모든 열과 모든 행을 돌리면, 처음 상태와 같기 때문)

이 문제를 완전탐색으로 푸는 방법으로 방향을 잡았다.

행과 열을 뒤집는 모든 경우를 따져봤을 때, target과 같은 모양이 되면 그 경우 중 가장 작은 수를 반환하는 완전탐색을 한다고 하면, 이는 O(2^{가로의 길이} * 2^{세로의 길이}) = O(2^n*m) 이다.

가로와 세로의 길이가 10을 넘지 않기 때문에, 충분히 해결 가능한 시간복잡도라고 생각했다.

 

다만, 다음의 조건에 따라 O(2^;n*n*m) = O(2ⁿ⁺¹)으로 줄일 수 있다.

 

열을 뒤집는 모든 경우에서, 각 경우에서의 모든 행은 다음 3가지 경우의 수 중 한 가지이다.

1. 행 전체가 해당하는 target의 행과 일치한다.
2. 행 전체가 해당하는 target의 행과 일치하지 않는다.
3. 행의 일부는 target의 행과 일치하고, 일부는 일치하지 않는다. 

1번의 경우, 해당 행을 뒤집을 필요가 없다.

2번의 경우, 해당 행을 뒤집어야 한다.

3번의 경우에 해당하는 행이 하나라도 있으면, target으로 바꿀 수 없다.

 

열을 뒤집는 모든 경우에서, 모든 행에 대한 이 조건을 확인하면, 뒤집는 횟수와 beginning을 target으로 바꿀 수 있는지를 확인할 수 있다.

 

코드

우선 beginning과 target에서 다른 부분을 찾아 true 혹은 false로 배열을 만들어, 이 배열을 true로 채우는 것으로 문제를 바꾸어 풀었다. 

열을 바꾸는 모든 경우의 수는 (2^{열의 개수})를 이진수로 바꾸어 비트마스크(XOR)를 통해 구하였다.

column[i]	reverse[i]	result
TRUE	TRUE	FALSE
TRUE	FALSE	TRUE
FALSE	TRUE	TRUE
FALSE	FALSE	FALSE

 

fun solution(beginning: Array<IntArray>, target: Array<IntArray>): Int {
    val diff = buildDiff(beginning, target)

    var minValue = Int.MAX_VALUE
    for(bit in 0 until 2.0.pow(diff[0].size).toInt()) {
        val bitMask = bit.toString(2).padStart(diff[0].size, '0').toList().map { it=='1' }
        var result = true
        var needColumnReverse = 0

        for(i in diff.indices) {
            for(j in 1 until diff[0].size) {
                if(bitMask[0] xor diff[i][0] != bitMask[j] xor diff[i][j]) {
                    result = false
                }
            }
        }
        for(i in diff.indices) {
            if(!(bitMask[0] xor diff[i][0])) needColumnReverse++
        }
        if(result) {
            minValue = min(minValue, bitMask.count { it } + needColumnReverse)
        }
    }
    return if(minValue==Int.MAX_VALUE) -1 else minValue
}

fun buildDiff(beginning: Array<IntArray>, target: Array<IntArray>): MutableList<MutableList<Boolean>> {
    val diff = arrayListOf<MutableList<Boolean>>()
    for(i in beginning.indices) {
        diff.add(arrayListOf())
        for(j in beginning[0].indices) {
            diff[i].add(beginning[i][j] == target[i][j])
        }
    }
    return diff
}