백준 1080. 행렬

행렬

생각보다 어려웠던 그리디 문제

1. 간단 설명

---

0과 1로만 이루어진 행렬 A, B이 주어진다

000    111
000 -> 111
000    111

행렬을 뒤집으면 3x3만큼 다같이 뒤집어진다

행렬 A를 B로 바꾸는데 필요한 연산 회수의 최소값 구하기

2. 예시

---

예제 1)

3 3

111 <- 행렬 A
111
111

000 <- 행렬 B
000
000

(0,0)부터 3x3만큼 뒤집으면 한번에 A->B 변환 가능

예제 2)

1 1
1
0

-1

불가능?

행렬의 크기가 3보다 작으면 뒤집기 자체가 불가능한것으로 판단하는 듯 하다

크기가 3x3보다 작다면 무조건 -1을 출력하도록 세팅해야할듯함

예제 3)

3 4
0000
0010
0000
1001
1011
1001

0000    0111    1001
0010 -> 0101 -> 1011
0000    0111    1001

첫번째 (0,1)에서 3x3만큼, 두번째 (0,0)에서 3x3만큼 뒤집으면 가능

3. 알고리즘

---

첫번째 아이디어

(0,0)~(N-3, M-3)까지 가능한 경우의수를 모두 뒤집어봄

최대 (50,50) 행렬이므로, (0,0)~(47,47) 중 하나의 좌표를 잡고 뒤집고, 정답이 나올때까지 뒤집어본다

-> (47*47)!인데, 시간상 절대 2초 내에 불가능

브루트포스 외에 다른 아이디어가 필요하다

두번쨰 아이디어

왜 그리디 문제일까

왼쪽 위부터 오른쪽 아래로 순서대로 B를 만들면서 뒤집어 나가면 가능하지 않을까?

즉, 첫번째 아이디어 브루트포스처럼 랜덤한 좌표를 골라서 뒤집는것이 아니라, 좌상단부터 순서대로 맞춰가는 것

A[y][x] != B[y][x]라면 해당 좌표는 무조건 뒤집어야한다

이후 옆칸으로 이동하면 옆에서 뭔짓을 하던간에, 이 좌표는 영향을 받지 않으므로 순차적인 진행이 가능하다

1. N, M 입력받기
2. 행렬 A, B 입력받기
3. (0,0) 부터 (N-3, M-3)까지 A의 해당 원소를 B와 비교한다
	3-1. 만약 같다면 패스
	3-2. 같지 않다면 해당 좌표부터 3x3을 뒤집는다. 뒤집은 회수도 기록한다
	3-3. (N-3, M-3)까지 다 체크했다면 루프 종료
4. 행렬 A와 B가 같은지 체크한다
	4-1. 같다면 뒤집은 회수 출력
	4-2. 다르다면 -1 출력

필요 변수

• int N, M : 행렬의 크기
• vector<string> A, B : 행렬 A, B
• int flip_cnt : 뒤집은 회수
• bool Flip(int yy, int xx) : (yy,xx) 부터 3x3을 뒤집는 함수

4. 소스코드

---

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

using namespace std;

int N, M;
vector<string> A, B;

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;
	A.resize(N);
	B.resize(N);
	for (int y = 0; y < N; y++) {
		cin >> A[y];
	}
	for (int y = 0; y < N; y++) {
		cin >> B[y];
	}
}

// 배열 A의 (yy,xx)의 좌표부터 3x3을 뒤집는 함수
// 불가능하면 false를 리턴한다
bool Flip(int yy, int xx) {
	if (yy < 0 || xx < 0 || yy > N - 3 || xx > M - 3) return false;
	
	for (int y = yy; y < yy + 3; y++) {
		for (int x = xx; x < xx + 3; x++) {
			if (A[y][x] == '0') {
				A[y][x] = '1';
			}
			else {
				A[y][x] = '0';
			}
			
		}
	}

	return true;
}

int main() {
	Input();
	
	int flip_cnt = 0;

	// (0,0) ~ (N-3, M-3)까지 체크
	// N, M이 2보다 작으면 아예 뒤집기 시도 안함
	for (int y = 0; y <= N - 3; y++) {
		for (int x = 0; x <= M - 3; x++) {
			if (A[y][x] != B[y][x]) {
				Flip(y, x);
				flip_cnt++;
			}
		}
	}
	
	if (A == B) {
		cout << flip_cnt;
	}
	else {
		cout << -1;
	}


	return 0;
}

줄별로 비교하는 방법을 떠올려서 각 열을 비교하는 방식으로 도전했다가 실패했다

이후 각 원소 자체를 비교하는 방법으로 시도해서 성공