Baekjoon 1080 행렬

Link https://www.acmicpc.net/problem/1080

소스결과 1992 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 그리디 알고리즘

 

설명

0과 1로 이루어진 행렬 A B에 대해서 특정 연산을 통해 A를 B로 바꾸는 연산의 최솟값을 구하는 프로그램을 만들자.

 

처음에는 이 문제가 왜 그리디 알고리즘인지 궁금했다. 질문 게시판에는 이미 같은 생각을 가진 다른사람이 있었다.

0,0을 뒤집을 수 있는 경우는 0,0에서 연산을 하는 경우밖에 없다.

따라서 특정 위치는 뒤집을 수 있는 경우의 수가 9보다 작은 경우가 존재한다.

0,0 부터 가로로 확인하면서 뒤집는 수와, 세로로 확인하면서 뒤집는 수를 구해, 둘중에 한군데라도 가능하다면 결과값을 비교해 출력한다.

 

알고리즘

1. 행렬 A, B를 입력 받는다.

2. 0,0 부터 가로, 세로로 나누어 진행하며, 현재 탐색하는 위치의 값이 같지 않다면 현재위치로부터 가로, 세로 3칸을 반전 시킨다.

3. 목적 지점까지 반전하는 경우를 진행 하고. A와 B가 일치하는지 검사하여 일치하지 않는다면 불가능한 경우로 판단한다.

4. 가로를 먼저 시작한 경우와 세로를 먼저 시작한 경우 중 불가능한 경우를 제외하여 작은 값을 출력한다. 만약 둘중 한군데만 불가능 하다면 가능한 경우의 수를 출력한다. 둘 다 불가능한 경우 -1을 출력한다.

 

소스코드

#include <iostream>

using namespace std;

const short MAX = 50;

bool board[MAX][MAX];
bool target[MAX][MAX];

void invert(bool board[MAX][MAX], int sX, int sY)
{
	for (int r = 0; r < 3; r++)
		for (int c = 0; c < 3; c++)
			board[sX + r][sY + c] = !board[sX + r][sY + c];
}

int solveHorizon(int n, int m)
{
	int res = 0;
	bool temp[MAX][MAX] = {};

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			temp[i][j] = board[i][j];

	for (int i = 0; i < n - 2; i++)
		for (int j = 0; j < m - 2; j++)
		{
			if (temp[i][j] ^ target[i][j])
			{
				invert(temp, i, j);
				res++;
			}
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (temp[i][j] != target[i][j])
				return -1;

	return res;
}

int solveVertical(int n, int m)
{
	int res = 0;
	bool temp[MAX][MAX] = {};

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			temp[i][j] = board[i][j];

	for (int i = 0; i < m - 2; i++)
	{
		for (int j = 0; j < n - 2; j++)
		{
			if (temp[j][i] ^ target[j][i])
			{
				invert(temp, j, i);
				res++;
			}
		}
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (temp[i][j] != target[i][j])
				return -1;

	return res;
}

int mMin(int a, int b) { return a < b ? a : b; }

int main()
{
	int n, m;
	int res = 0;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		char input[MAX + 1] = {};
		cin >> input;

		for (int j = 0; j < m; j++)
			board[i][j] = input[j] - '0';
	}

	for (int i = 0; i < n; i++)
	{
		char input[MAX + 1] = {};
		cin >> input;

		for (int j = 0; j < m; j++)
			target[i][j] = input[j] - '0';
	}

	int verRes = solveVertical(n, m);
	int horRes = solveHorizon(n, m);

	if (verRes == -1)
		res = horRes;
	else if (horRes == -1)
		res = verRes;
	else
		res = mMin(verRes, horRes);

	cout << res;

	return 0;
}