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

문제

한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다. 모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다. 동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다.

 

 

예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다. 그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다. 초기 상태에서 2행과 4행의 돌들을 뒤집으면, 두 번째 그림이 됩니다. 그 후, 2열, 4열, 5열의 돌들을 순서대로 뒤집는 다면, 총 5번의 동전 뒤집기를 통해 목표 상태가 되며, 이 경우가 최소인 경우입니다.

 

직사각형 모양의 공간에 놓인 동전들의 초기 상태를 나타내는 2차원 정수 배열 beginning, 목표 상태를 나타내는 target이 주어졌을 때, 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하는 solution 함수를 완성하세요. 단, 목표 상태를 만들지 못하는 경우에는 -1을 return 합니다.

---

입력

• 1 ≤ beginning의 길이 = target의 길이 ≤ 10
• 1 ≤ beginning[i]의 길이 = target[i]의 길이 ≤ 10
  • beginning[i][j]와 target[i][j]는 i + 1행 j + 1열의 동전의 상태를 나타내며, 0 또는 1의 값으로 주어집니다.
  • 0은 동전의 앞면을, 1은 동전의 뒷면을 의미합니다.

---

처음엔 뒤집을 수 있는 모든 경우의 수를 따져보고자 했다.

먼저, 모든 행에서 뒤집거나 뒤집지 않는 행위 중 하나를 선택하고 모든 행에서 행동을 선택 했다면

이후, 모든 열에서 뒤집거나 뒤집지 않는 행위 중 하나를 선택하여 가능한 모든 경우를 확인하는 것이다.

즉, 아래와 같이 모든 경우를 따지는 것이다.

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기 X

1열 뒤집기 X -> 2열 뒤집기 X -> ... -> n-1열 뒤집기 X -> n열 뒤집기 X

 

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기 X

1열 뒤집기 X -> 2열 뒤집기 X -> ... -> n-1열 뒤집기 X -> n열 뒤집기

 

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기 X

1열 뒤집기 X -> 2열 뒤집기 X -> ... -> n-1열 뒤집기 -> n열 뒤집기 X

 

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기 X

1열 뒤집기 X -> 2열 뒤집기 X -> ... -> n-1열 뒤집기 -> n열 뒤집기

.

.

.

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기 X

1열 뒤집기 -> 2열 뒤집기 -> ... -> n-1열 뒤집기 -> n열 뒤집기

 

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기

1열 뒤집기 X -> 2열 뒤집기 X -> ... -> n-1열 뒤집기 X -> n열 뒤집기 X

 

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기

1열 뒤집기 X -> 2열 뒤집기 X -> ... -> n-1열 뒤집기 X -> n열 뒤집기

 

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기

1열 뒤집기 X -> 2열 뒤집기 X -> ... -> n-1열 뒤집기 -> n열 뒤집기 X

 

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기

1열 뒤집기 X -> 2열 뒤집기 X -> ... -> n-1열 뒤집기 -> n열 뒤집기

.

.

.

1행 뒤집기 X -> 2행 뒤집기 X -> ... -> n-1행 뒤집기 X -> n행 뒤집기

1열 뒤집기 -> 2열 뒤집기 -> ... -> n-1열 뒤집기 -> n열 뒤집기

 

총 경우의 수는 각 행과 열에서 취할 수 있는 행동이 2가지 이기 때문에

행을 뒤집는 경우의 수 2^n * 열을 뒤집는 경우의 수 2^n  = 2^2n이 되고 이 경우 시간 초과가 발생한다.

잘 생각해 보면 2^n으로 문제를 해결할 수 있는데 굳이 열에서 뒤집거나 뒤집지 않는 행동을 선택할 필요가 없기 때문이다.

 

문제 예시를 통해 이해해보자

 

 

오른쪽은 처음 상태에서 1, 3, 5행은 뒤집지 않고 2, 4행만 뒤집은 상태이다.

이 상태에서 우리는 굳이 열을 뒤집거나 뒤집지 않는 행동을 다시 취해봐야 하는가?

그렇지 않다. 우리의 목적은 목표 TARGET과 동일하게 만드는 것이므로 

오른쪽 상태에서 1열부터 n열까지 모든 열을 살펴보며

1)해당 열이 전부 TARGET과 반대인 경우

2)해당 열이 전부 TARGET과 동일한 경우

3) 1), 2)를 모두 만족하지 않는 경우

를 따져보는 것으로 현재 상태에서 TARGET과 동일하게 만들 수 있는지 없는지 판단이 가능하다.

1)의 경우 해당 열을 뒤집으면TARGET과 동일해지고

2)의 경우 해당 열을 뒤집지 않으면 TARGET과 동일해지며

3)의 경우가 하나의 열에서라도 발견되면 현재 상태에서는 어떻게 열을 뒤집어도 TARGET과 동일하게 만들 수 없다.

 

 

이 경우 3)의 상황은 발생하지 않았으므로

2, 4, 5열을 뒤집어주면 TARGET과 동일하게 만다는 것이 가능해는 것을 알 수 있다.

 

구현 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, ans = 11;
vector<vector<int>> beginning, target;

void flip_row(int r) {
    for (int j = 0; j < m; j++)
        //beginning[r][j] = (beginning[r][j] + 1) % 2;
        beginning[r][j] = !beginning[r][j];
}

int compare_colunm(int c) {
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (beginning[i][c] == target[i][c]) cnt++;

    if (cnt == 0) return 1; //1) 해당 열(=c)에서 beginning과 target 전부 반대인 경우
    if (cnt == n) return 0; //2) 해당 열(=c)에서 beginning과 target 전부 동일한 경우
    else return -1; //3) 1), 2)가 아닌 경우
    return true;
}

void dfs(int r, int cnt) {
    //모든 행에서 뒤집거나 뒤집지 않는 선택을 완료한 경우
    if (r == n) {
        int flag = 1;
        //열의 상태를 비교하여 TARGET과 동일하게 만들 수 있는지 판별
        for (int j = 0; j < m; j++) {
            int ret = compare_colunm(j);
            if (ret == -1) { flag = 0; break; } //현재 상태에서 TARGET과 동일하게 만들 수 없음 -> flag = 0;
            cnt += ret;
        }
        if (flag) ans = min(ans, cnt); //TARGET과 동일하게 만들 수 있는 경우 최소 뒤집기 횟수 갱신
        return;
    }
    if (r != n) {
        dfs(r + 1, cnt); //해당 행 뒤집기 X
        flip_row(r);
        dfs(r + 1, cnt + 1); //해당 행 뒤집기
        flip_row(r);
    }

}

int solution(vector<vector<int>> _beginning, vector<vector<int>> _target) {
    beginning = _beginning; target = _target;
    n = beginning.size(); m = beginning[0].size();
    dfs(0, 0);
    if (ans == 11) return -1;
    return ans;
}