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

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

프로그래머스

처음 문제를 확인했을 때 제한사항이 그렇게 크지 않아서 전체 탐색으로 풀려고 했었음, 하지만 문제에 대한 잘못된 이해임을 깨달은 후 다른 방법을 모색함

 

두 배열의 다른 부분을 나타내는 배열을 만들고 이 배열을 모두 0으로 만들면 목표상태와 같아짐

 

XOR의 특성을 이해하면 쉽게 풀 수 있는 문제였지만 특성을 알지 못해 친구에게 힌트를 얻어 문제를 풀이함

 

각 행 또는 열을 두 번 이상 바꾸는 것은 최소 뒤집기가 되지 않음 따라서 한 행 또는 열을 한 번씩만 뒤집어 모두 0을 만들 수 있어야 함

 

만약 모두 뒤집었을 때 모두 0이 아니라면 목표 상태를 만들지 못하는 경우임

 

이렇게 해서 행 -> 열 또는 열 -> 행 순서로 반복문을 돌아 첫 번째 인자가 1이라면 뒤집기를 실행하면 됨

 

위와 같이 풀었을 때 실패하는 테스트 케이스가 존재하는 데 아래와 같은 경우임

[[ 0, 1, 1 ],
  [ 1, 0, 0 ]]

 

풀이 방식대로 하면 행을 시작으로 하던 열을 시작으로 하던 3의 값이 도출됨, 하지만 최솟값은 첫 번째 열을 바꾸고 첫 번째 행을 바꾸어 총 2의 값임

 

여기서 XOR 뒤집기의 또 다른 특성이 있는데 모든 뒤집기 경우의 수에서 현재 구한 경우의 수를 제외한 나머지로 동일한 결괏값을 도출할 수 있음

[ 0, 0 ] -> [ 0, 1 ]을 만들 때
케이스 1: 열 2를 뒤집어서 만들 수 있음, 총 1번
케이스 2: 행을 뒤집고 열 1을 뒤집으면 만들 수 있음, 총 2번
케이스 1과 2를 합치면 뒤집을 수 있는 모든 경우의 수가 됨

[[ 0, 0, 0 ],   ->   [[ 0, 1, 1 ], 
  [ 0, 0, 0 ]]          [ 1, 0, 0 ]]
케이스 1: 행 1을 뒤집고 열 1을 뒤집음, 총 2번
케이스 2: 행 2를 뒤집고 열 2,3을 뒤집음, 총 3번
뒤집을 수 있는 모든 경우의 수 5번은 케이스 1과 2를 합친 값과 같게 됨

 

따라서 구한 경우의 수와 전체 경우의 수에서 뺀 값을 비교하여 더 작은 수를 대입함

 

그리디 한 문제를 주로 dfs로 이용하여 풀이하려는 버릇이 있음, 만약 둘 중 고민된다면 그리디가 정답 도출까지 시간이 덜 걸리므로 먼저 풀이한 후 맞지 않으면 탐색 형식으로 풀어야 할 듯

function solution(beginning, target) {
    var answer = 0;
    let diff = beginning.map((row, rIdx) => {
        const targetRow = target[rIdx];
        
        return row.map((col, cIdx) => col != targetRow[cIdx] ? 1 : 0)
    })
    
    const rowCnt = diff.length;
    const colCnt = diff[0].length;
    
    for(let c = 0; c < diff[0].length; c++){
        if(!diff[0][c]) continue;
        answer += 1;
        diff = diff.map((row, rIdx) => {
            return row.map((col, cIdx) => cIdx == c ? +!col : +col);
        })
    }
    
    for(let r = 0; r < diff.length; r++){ 
        if(!diff[r][0]) continue;
        answer += 1;
        diff = diff.map((row, rIdx) => {
            return rIdx == r ? row.map(it => +!it) : row;
        })
    }

    let isResolve = true;
    
    diff.forEach((row) => {
        row.forEach((col) => {
            isResolve &&= !col;
        })
    })
    
    if(!isResolve) return -1;
    
    return Math.min(answer, rowCnt + colCnt - answer);
}