(C#) 2차원 동전 뒤집기

https://school.programmers.co.kr/learn/courses/30/lessons/131703?language=csharp#

프로그래머스

 

 사실상 1행과 1열만 보면 된다.

 문제에서 보여주는 예시이다.

 

 주어진 동전을 무턱대고 뒤집기보다는, 어떤 동전을 뒤집어야하는지를 먼저 파악해두자.

 동전의 시작 배치와 목표 배치의 차이만을 기록하는 2차원 불리안 배열 bool[ , ] diff를 만들어준다.

 diff의 각 (i, j)요소에는 beginning[i, j] == target[i, j]를 담는다. 즉, diff[i, j]가 false이면 (i, j)의 동전을 뒤집어야 한다는 뜻이다.

 

 예시의 경우 diff를 생성하면 다음과 같을 것이다.

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

 diff의 모든 요소를 1로 바꿀 수 있으면 된다.

 

 그렇다면 어떻게 diff의 모든 요소를 1로 바꿀 수 있을까?

 

 먼저 1행의 값들을 모두 1로 바꿔보자. 1행의 요소 중 0인 열을 모두 뒤집는다.

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

 그랬더니, 이럴수가, 각 행의 모든 요소가 똑같아졌다!

 그렇다면 이제는 값이 0인 행들을 뒤집으면 된다.

 

 왜 이렇게 되는지는 스스로 알아보자. 아무튼 이렇게 되기 때문이다.

 

 하지만 한가지 주의해야 하는 점이 있는데, 바로 행과 열 중 어느 방향을 먼저 뒤집느냐는 것이다.

 위의 예시에서는 행과 열, 어느 방향을 먼저 뒤집더라도 결과가 달라지지 않는다.

 하지만 다른 예시를 들어보자.

 

 diff가 다음과 같은 경우를 살펴보자.

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

 이 경우 누가 봐도 1행만 뒤집으면 된다.

 그러나 열을 먼저 뒤집기로 한다면 총 9번을 뒤집어야한다.

 따라서 행과 열, 어느 방향을 먼저 뒤집는지를 살펴봐야 한다.

 

 사실 이 부분도 간단하게 계산할 수 있다.

 행의 갯수를 col, 열의 갯수를 row, 행부터 뒤집는 방법의 횟수가 n, 열부터 뒤집는 방법의 횟수가 m이라고 하면, 다음과 같은 식이 성립한다.

 n + m = col + row

 

 즉, m = col + row - n이고, answer = Math.Min(n, col + row - m)을 해주면 된다.

 왜 이렇게 되는지는 스스로 알아보자. 아무튼 이렇게 된다.

 

 결과적으로 답을 구하기 위해서는 1행과 1열에 대해서 diff의 모든 0을 1로 바꿔주는 작업을 해주면 된다.

 작업을 했는데 diff에 0이 남아있다면 그것은 불가능한 경우이기 때문에 -1을 반환해준다.

코드

using System;

public class Solution {
    public int solution(int[,] beginning, int[,] target)
    {
        int answer = 0;
        int col = beginning.GetLength(0);
        int row = beginning.GetLength(1);

        // beginning과 target의 차이
        bool[,] diff = new bool[col, row];
        for (var i = 0; i < col; i++)
        {
            for (var j = 0; j < row; j++)
            {
                // true: 같음, false: 다름
                diff[i, j] = beginning[i, j] == target[i, j];
            }
        }

        for (var i = 0; i < col; i++)
        {
            if (!diff[i, 0])
            {
                for (var j = 0; j < row; j++)
                {
                    diff[i, j] = !diff[i, j];
                }
                answer++;
            }
        }
        for (var j = 0; j < row; j++)
        {
            if (!diff[0, j])
            {
                for (var i = 0; i < col; i++)
                {
                    diff[i, j] = !diff[i, j];
                }
                answer++;
            }
        }

        for (var i = 0; i < col; i++)
        {
            for (var j = 0; j < row; j++)
            {
                if (!diff[i, j]) return -1;
            }
        }
        answer = Math.Min(answer, col + row - answer);
        return answer;
    }
}