[백준 | 파이썬] 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을 출력한다.

풀이 방법

가장 첫번째 칸부터 시작해서 A와 B가 달라지면 그 칸을 기준으로 오른쪽 방향으로 총 3칸, 아래쪽 방향으로 총 3칸 뒤집는다.

뒤집기를 전부 수행한 다음, A와 B 가 모두 일치하는지 확인하고 뒤집은 갯수를 출력한다. 아닌 경우 -1을 반환한다.

코드

# n행 m열
n, m = map(int, input().split())
A = [list(map(int, input())) for _ in range(n)]
B = [list(map(int, input())) for _ in range(n)]

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

def check():
    for i in range(n):
        for j in range(m):
            if A[i][j] != B[i][j]:
                return False
    return True

cnt = 0
for i in range(n-2):
    for j in range(m-2):
        if A[i][j] != B[i][j]:
            reverse(i, j)
            cnt += 1

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