행렬 1080

문제 해설 및 주의사항

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

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

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

---

 

풀이

※ 0 -> 1 로 바꾸는 문제들

- flip 하는 연산을 다룰 때, 명심해야 할 점은 연산은 0번 하거나 1번 할 때만 의미가 있다. 2번 하면 원래대로 돌아오기 때문이다.

 

1. 총 연산

- 2^(NM) 이므로(N <= 50, M <= 50), 브루트 포스는 절대 불가능하다.

 

2. 맨 왼쪽 상단 칸만을 보자.- 맨 왼쪽 상단 칸(0,0) 을 바꿀 수 있는 방법은 하나밖에 없다. 이것을 결정하고 (0, 1)을 결정하고..

 

---

풀이코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <tuple>
using namespace std;
// 행렬 1080

const int MAX = 50;

int from[MAX][MAX];
int to[MAX][MAX];

void flip(int x, int y){
	for(int i = x - 1; i <= x + 1; i++){
		for(int j = y - 1; j <= y + 1; j++){
			from[i][j] = 1 - from[i][j];
		}
	}
}

int main(){
	
	// 입력
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++){
		for(int j = 0 ; j < m; j++){
			scanf("%1d", &from[i][j]);
		}
	}
	 for (int i=0; i<n; i++) {
 		for (int j=0; j<m; j++) {
			scanf("%1d",&to[i][j]);
 		}
 	}
	int ans = 0;
	for(int i = 0; i < n - 2; i++){
		for(int j = 0; j < m - 2; j++){
			// 3x3 박스의 맨 왼쪽 부분만을 비교하여, 같으면 두고, 다르면 flip 한다.
			if(from[i][j] != to[i][j]){
				ans += 1;
				flip(i + 1, j + 1);
			}
		}
	}
	
	// 전체 비교
	for (int i=0; i<n; i++) {
 		for (int j=0; j<m; j++) {
 			if (from[i][j] != to[i][j]) {
 				printf("-1\n");
 				return 0;
 			}
 		}
 	}	
	
 	printf("%d\n",ans);
}

 

---

퇴고