문제이해 💬

백준 1080번 행렬

행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값
(연산 = 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0))

처음 든 생각 🙋‍♀️

문제 디테일 : 부분 행렬

3X3 부분행렬의 모든 원소를 뒤집기?
부분 행렬이란?

문제 디테일 : 여러번 switch

0을 1로 바꾼걸 다시 0으로 바꾸고
이런 게 아예 없진 않을 것 같다.
이걸 고려하지 않으면 잘못 식을 세울 수도 있을 것 같다.

사람의 생각 흐름

0000
0010
0000

1001
1011
1001

을 예시로 봤을때,
1. 바꿔야 할 영역 체크
2. 바꿔야 할 영역을 iXj (단, i, j <= n,m, 3) 으로 나눈다.
3. 이렇게 만들어지는 부분 영역 iXj 의 갯수 최대한 적게 하고, 그 수를 구해야.
4. 단, 여러번 swtich 경우 고려

첫번째 고려

BFS?
최대한 적은 수를 구한다고 하니까

greedy
greedy는 항상 최적의 해를 보장함을 검증해야한다.

두번째 고려

내가 아예 문제를 잘못 이해했다!
어떤 (3×3크기의 부분 행렬)에 있는 모든 원소를 뒤집는 것 인데
(=무조건 3*3 으로만 뒤집을 수 있음)

어떤 (3×3크기)의 부분 행렬에 있는 모든 원소를 뒤집는 것 로 이해했다.
(= i*j 부분배열을 뒤집을 수 있으며, i, j <= 3임)

세번째 생각

참고한 블로그에서 다음과 같이 설명했다.

(0,0) (N-1,0), (0, M-1), (N-1,M-1)의 값을 결정할 수 있는 부분행렬은 딱 1개밖에 존재하지 않는다.
즉, (0,0)에서 3x3 매트릭스를 그려서, A[0][0] != B[0][0] 이라면 3x3 매트릭스에 해당하는 값을 전부 뒤집는다.
이제, (0,1)에 영향을 주는 매트릭스는 (0,1)을 꼭지점으로 하는 매트릭스 하나뿐이다. 마찬가지로 A[0][1] != B[0][1]을 확인한다.

위의 전제가 확실하게 도출되어야 (=최적해를 보장해야)
그리디로 풀 수 있다는생각이 든다!

코드👩🏻‍💻

N, M =map(int,input().split())

A = [list(map(int,list(input()))) for _ in range(N)]
B = [list(map(int,list(input()))) for _ in range(N)]

def flip(x,y):
    for i in range(x,x+3):
        for j in range(y,y+3):
            A[i][j] = 1 - A[i][j]

def checkEquality():
    for i in range(N):
        for j in range(M):
            if A[i][j] !=B[i][j]:
                return 0
    return 1

cnt = 0
for i in range(0,N-2):
    for j in range(0,M-2):
        if A[i][j] !=B[i][j]:
            flip(i,j)
            cnt+=1

if checkEquality():
    print(cnt)
else:
    print(-1)