2차원 동전 뒤집기 (with Kotlin)

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

프로그래머스

이 문제는 DFS를 활용해서 모든 경우를 탐색하도록 의도된 문제로 보인다.
시간 복잡도 측면에서는 더 효율적인 풀이가 있을 수도 있지만, 문제의 본래 의도를 따라 푸는 것이 더 바람직하다고 생각한다.

 

import kotlin.math.min

var answer: Int? = null

fun Array<IntArray>.flip(row: Int) {
    for (col in this[0].indices) {
        this[row][col] = this[row][col] xor 1
    }
}

class Solution {
    fun flatCount(graph: Array<IntArray>, target: Array<IntArray>): Int? {
        var flatCount = 0
        
        for (col in graph[0].indices) {
            val matchCount = graph.indices
                .count { row -> graph[row][col] == target[row][col] }

            when {
                matchCount == 0 -> flatCount++
                matchCount < graph.size -> return null
            }
        }
        
        return flatCount
    }
    
    fun dfs(graph: Array<IntArray>, target: Array<IntArray>, level: Int, count: Int) {
        if (level == graph.size) {
            flatCount(graph, target)?.let {
                answer = min(answer ?: Int.MAX_VALUE, count + it)
            }

            return
        }
        
        dfs(graph, target, level + 1, count)
        graph.flip(level)
        dfs(graph, target, level + 1, count + 1)
        graph.flip(level)
    }
    
    fun solution(beginning: Array<IntArray>, target: Array<IntArray>): Int {
        dfs(beginning, target, 0, 0)
        return answer ?: -1
    }
}