teddy8 Full Stack Software Engineer

[BaekJoon][Greedy] 1080. 행렬

2019-07-04
teddy8

문제

URL : https://www.acmicpc.net/problem/tag/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98


문제 설명

/* 문제 : [1080] 행렬
[input]
3 4
0000
0010
0000
1001
1011
1001
[output]
2
[설명]
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 
연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 
둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
*/

소스코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void changeArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2, int x, int y);
bool CompareTwoArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2);
void inputArray(vector<vector<int>> &arr);	// 2차원 배열에 데이터 입력
void outputArray(vector<vector<int>> &arr);

int main()
{
	int n, m;	// 행렬의 크기 n, m
	int count = 0; // 연산횟수 누적
	bool isEqual = false;
	cin >> n >> m;
	vector<vector<int>> arr1(n, vector<int>(m, 0));
	vector<vector<int>> arr2(n, vector<int>(m, 0));
	inputArray(arr1);
	inputArray(arr2);

	for (int i = 0; i <= (n - 3) && !isEqual; i++) {
		for (int k = 0; k <= (m - 3) && !isEqual; k++) {
			if (arr1[i][k] == arr2[i][k]) // 바꿀 필요 없으면 패스
				continue;

			changeArray(arr1, arr2, i, k);
			count++;
			isEqual = CompareTwoArray(arr1, arr2);
		}
	}

	if (CompareTwoArray(arr1, arr2) == true)
		cout << count;
	else
		cout << "-1";

	return 0;
}

bool CompareTwoArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2) {
	for (int i = 0, n; i < arr1.size(); i++) {
		for (int k = 0; k < arr1[i].size(); k++) {
			if (arr1[i][k] != arr2[i][k])
				return false;
		}
	}
	return true;
}

void changeArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2, int x, int y) {
	for (int i = x; i < (x + 3); i++) { // 3x3범위의 모든 원소 반전 (1->0, 0->1)
		for (int k = y; k < (y + 3); k++) {
			arr1[i][k] = (1 - arr1[i][k]);
		}
	}
}

void inputArray(vector<vector<int>> &arr) {
	string s;
	for (int i = 0, n; i < arr.size(); i++) {
		cin >> s;
		for (int k = 0; k < arr[i].size(); k++) {
			arr[i][k] = s[k] - '0';
		}
	}
}

void outputArray(vector<vector<int>> &arr) { // 디버깅용
	for (int i = 0, n; i < arr.size(); i++) {
		for (int k = 0; k < arr[i].size(); k++) {
			cout << arr[i][k];
		}
		cout << endl;
	}
}

Comments

Content