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

이 문제는 백트래킹을 이용해서 풀었다.

 

이 문제에서 핵심은 각 행과 열이 최대 한 번씩만 뒤집는 경우로 제한하는 것과 뒤집는 순서가 바뀌어도 결과가 같다는 것이다.

우선 아래의 숫자에서 2행 -> 1열 을 뒤집고, 같은 숫자에서 1열 -> 2행을 뒤집으면 같은 결과가 나온다.

10111		10111
01010		10101
10001	->2행	10001
01001		01001
10101		10101

1열		1열
	
00111		00111
11010		00101
00001	->2행	00001
11001		11001
00101		00101

이를 파악함으로써 뒤바뀐 순서를 다시 탐색하지 않도록 count를 두어 순서를 강제함으로써 속도를 높일 수 있다.

 

두 번째로 같은 행, 열을 2번 뒤집으면 원래 모양이 나오기 때문에 딱 1번만 뒤집는 경우로 최대 뒤집기 수를 제한할 수 있다.

 

이 두 가지를 구현하면 정답을 맞출 수 있다. 그러나 비트마스킹을 쓰면 더 빠르게 만들 수 있을 것 같긴 하다.

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

#define MAX 10
#define INF 1000000000

vector<vector<int>> target;
int maxRow;
int maxColumn;
int rowCount[MAX];
int columnCount[MAX];

bool isSame(vector<vector<int>> coins)
{
    for (int y = 0; y < maxRow; y++)
    {
        for (int x = 0; x < maxColumn; x++)
        {
            if (coins[y][x] != target[y][x])
            {
                return false;
            }
        }
    }
    return true;
}

vector<vector<int>> rowFlip(vector<vector<int>> coins, int y)
{
    vector<vector<int>> result = coins;
    for (int x = 0; x < maxColumn; x++)
    {
        if (coins[y][x] == 0)
        {
            result[y][x] = 1;
        }
        else
        {
            result[y][x] = 0;
        }
    }
    return result;
}

vector<vector<int>> columnFlip(vector<vector<int>> coins, int x)
{
    vector<vector<int>> result = coins;
    for (int y = 0; y < maxRow; y++)
    {
        if (coins[y][x] == 0)
        {
            result[y][x] = 1;
        }
        else
        {
            result[y][x] = 0;
        }
    }
    return result;
}

int solve(vector<vector<int>> coins, int prev)
{
    if (isSame(coins))
    {
        return 0;
    }
    // rowFlip
    int count = 0;
    int result = INF;
    for (int y = 0; y < maxRow; y++)
    {
        count++;
        if (rowCount[y] == 0 && count >= prev)
        {
            rowCount[y]++;
            vector<vector<int>> flip = rowFlip(coins, y);
            result = min(result, solve(flip, count) + 1);
            rowCount[y]--;
        }
    }
    // columnFlip
    for (int x = 0; x < maxColumn; x++)
    {
        count++;
        if (columnCount[x] == 0 && count >= prev)
        {
            columnCount[x]++;
            vector<vector<int>> flip = columnFlip(coins, x);
            result = min(result, solve(flip, count) + 1);
            columnCount[x]--;
        }
    }
    return result;
}

int solution(vector<vector<int>> beginning, vector<vector<int>> targ) {
    target = targ;
    maxRow = targ.size();
    maxColumn = targ[0].size();
    int answer = solve(beginning, -1);
    if (answer == INF)
    {
        return -1;
    }
    return answer;
}