프로그래머스 Level 3 2차원동전뒤집기

2차원동전뒤집기 (프로그래머스 Level 3)

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

문제를 보고 곰곰히 생각해본 결과, 브루트 포스로 풀 수 있는 문제라 생각하였으나
(조건 : 길이 <= 10)
막상 구현에서 답이 막혀버렸다
‘가능한 모든 경우의 수를 탐색해야 하며’, ‘그것이 가능한지 여부를 체크’ 한다는 부분에
백기를 들었던 것 같다

검색을 해보니 비트마스킹과 간단한 수학적 지식을 통해 답을 이끌어내는 방식을 취할 수 있었는데

1. ‘모든 행 n개를 뒤집는 경우의 수’는 1 « n 이다 (2^n)
   
2. 각 경우의 수에 해당하는 mask 수를 ‘행’에 대하여 ‘비트마스킹’ 체크를 함으로서
   모든 행이 뒤집히는 각 경우의 수를 구할 수 있다
   => rowMask를 예로 들자면,
   rowMask : 1 ~ 1 « n 까지 반복
   반복문 i : 1 ~ n 까지 반복하며
   각 행이 뒤집히는 경우의 수를 체크(rowMask % (1 « i))
   rowMask가 0이면, 모든 행은 뒤집히지 않음(000)
   1이면, ‘첫’ 행만 뒤집힘 (001)
   2이면, ‘두번째 행만 뒤집힘 (010)
   …
   7이면 ‘1,2,3’ 행이 뒤집힘(111)
   

이런식으로 가능한 모든 행과 모든 열에 대하여
경우의 수를 구하는 문제이다

문제가 막막하더라도 좀 더 다양한 방법으로 생각을 해봐야겠다고 다시금 느끼게 되었다

Code

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// 행을 뒤집는 도우미 함수
void flipRow(vector<vector<int>>& matrix, int row)
{
	for (int j = 0; j < matrix[0].size(); j++)
	{
		matrix[row][j] = 1 - matrix[row][j];
	}
}

// 열을 뒤집는 도우미 함수
void flipColumn(vector<vector<int>>& matrix, int col)
{
	for (int i = 0; i < matrix.size(); i++)
	{
		matrix[i][col] = 1 - matrix[i][col];
	}
}

// 두 행렬이 동일한지 확인하는 함수
bool areEqual(const vector<vector<int>>& mat1, const vector<vector<int>>& mat2)
{
	for (int i = 0; i < mat1.size(); i++)
	{
		for (int j = 0; j < mat1[0].size(); j++)
		{
			if (mat1[i][j] != mat2[i][j])
			{
				return false;
			}
		}
	}
	return true;
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
	int n = beginning.size();
	int m = beginning[0].size();
	int answer = INT_MAX;

	// 모든 행 뒤집기 조합을 시도
	// 각 line의 모든 경우의 수가 1 << n이기에 이 이상 시도하였는데 발견하지 못하는 경우
	// 맞추는 것이 불가능하다 판단
	for (int rowMask = 0; rowMask < (1 << n); rowMask++)
	{
		vector<vector<int>> temp = beginning;
		int flipCount = 0;

		// rowMask를 기반으로 행을 뒤집기
		for (int i = 0; i < n; i++)
		{
			// rowMask가 1 ~ 1 << n 까지의 수를 '1'부터 증가하며 모든 경우의 수를 포함
			// 그걸 비트 마스킹을 통하여 '해당 번째 수'에서 '뒤집을 행'을 확인
			// -> 모든 '행'들이 각각 뒤집어 지는 경우의 수를 확인이 가능
			// 
			// 비트 마스킹 확인하기
			if (rowMask & (1 << i))
			{
				flipRow(temp, i);
				flipCount++;
			}
		}

		// 모든 열 뒤집기 조합을 시도
		for (int colMask = 0; colMask < (1 << m); colMask++)
		{
			vector<vector<int>> tempColFlip = temp;
			int currentFlipCount = flipCount;

			// colMask를 기반으로 열을 뒤집기
			for (int j = 0; j < m; j++)
			{
				if (colMask & (1 << j))
				{
					flipColumn(tempColFlip, j);
					currentFlipCount++;
				}
			}

			// 현재 구성과 target이 일치하는지 확인
			if (areEqual(tempColFlip, target))
			{
				answer = min(answer, currentFlipCount);
			}
		}
	}

	// 해결책을 찾지 못한 경우 -1 반환
	if (answer == INT_MAX)
	{
		return -1;
	}

	return answer;
}