백준 1080 파이썬 - 행렬

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

1080번: 행렬

문제

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

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

코드

import sys
n, m = map(int, sys.stdin.readline().split())
before = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(n)]
after = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(n)]
def check():
    for i in range(n):
        for j in range(m):
            if before[i][j] != after[i][j]:
                return False
    return True
def reverse(x, y):
    for i in range(x, x + 3):
        for j in range(y, y + 3):
            before[i][j] = 1 - before[i][j]
cnt = 0
for i in range(n - 2):
    for j in range(m - 2):
        if before[i][j] != after[i][j]:
            reverse(i, j)
            cnt += 1
sys.stdout.write(str(cnt) if check() else "-1")

풀이

어차피 두번째 행렬과 같아지려면 다른 부분은 한 번 이상 뒤집어야하기 때문에 다른 부분을 찾고 그 부분부터 가로 세로로 +2한 부분까지 다 뒤집는다. 계속 뒤집어보고 같아지지 않으면 -1을 출력하면 된다.