백준 1285 동전 뒤집기

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

N행 N열의 동전이 있으며, 각 동전은 앞면(H) 또는 뒷면(T)상태로 존재한다.

한 행이나 열을 선택하여 동전들을 뒤집을 수 있으며, 뒷면(T)의 개수가 최소가 되도록 돌렸을 때 뒷면의 개수를 출력하는 문제이다.

N이 최대 20이므로, 각 행이나 열을 모두 돌린다면 2^20 * 2^20 = 2^40번이기 때문에 시간 초과가 날 수 있다.

탐색을 줄일 수 있는 방법을 생각해 보았으나 쉽게 떠오르지 않아 구글링을 통해 아이디어를 얻어 풀었다.

핵심 아이디어는 행 or 열 중 하나만 완전탐색(2^20)을 하고, 각 탐색 케이스마다 최적이 되도록 열 or 행을 뒤집어 구하는 것이다.

말로만 들으면 이해가 가지 않을 수 있으니 주어진 예제를 따라가며 확인해 보자.

예시와 같은 테이블이다.

행을 완전탐색하고 열을 맞추는 방식으로 진행해보자.

맨 왼쪽의 기본 테이블에 대해 행을 뒤집는 경우는 오른쪽 7개의 필드와 같다.

그럼 이제 7개의 모든 행을 뒤집는 케이스에 대해, 뒷면이 적도록 열을 뒤집은 뒤 개수를 구하면 된다.

예를 들어 0번째 행만 뒤집은 케이스에 대해서, 0번째 열은 뒷면이 3개이므로 뒤집고, 1번째와 2번째 열은 뒷면이 1개이므로 놔 둔다.

이 경우에 뒷면은 2개이다.

이처럼 행을 뒤집는 모든 케이스의 각 열에 대해 min(T 개수, N - T 개수) 만큼을 합하면 된다.

다른 케이스를 한번 더 보자면, 0번째와 1번째 행을 뒤집은 위 경우에 모든 열을 뒤집는 것이 뒷면 개수를 줄이는 데 도움이 된다.

따라서 다 뒤집었을 때, 1 + 1 + 1 = 3으로 3개의 뒷면이 남게 된다.

이러한 방식으로 최솟값을 갱신하며 정답을 도출한다.

import kotlin.math.min

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val field = Array(N){readLine().toCharArray()}

    var answer = Int.MAX_VALUE

    fun dfs(r: Int){
        if(r >= N) return
        val t = countTWithFlipColumn(N, field)
        if(answer > t)
            answer = t

        for(i in r until N){
            flipRow(i, field)
            dfs(i + 1)
            flipRow(i, field)
        }
    }
    dfs(0)
    print(answer)
}

fun flipRow(r: Int, field: Array<CharArray>){
    for(i in field[r].indices){
        field[r][i] = if(field[r][i] == 'T') 'H' else 'T'
    }
}

fun countTWithFlipColumn(N: Int, field: Array<CharArray>): Int{
    var sum = 0
    for(i in 0 until N){
        var cnt = 0
        for(j in 0 until N){
            if(field[j][i] == 'T')
                cnt++
        }
        sum += min(cnt, N - cnt)
    }
    return sum
}