[BOJ] 1080 행렬 (Python3)

문제

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

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

입력

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

출력

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

예제

예제 출력 2
3 4
0000
0010
0000
1001
1011
1001

예제 출력 1
2

문제 풀이

그리디 알고리즘 문제이다. 근데 문제가 너무 그리디 써서 풀면 풀겠지~ 하고 풀면 풀려서 조금 그랬다… 무조건 3*3을 뒤집는다는것 부터 그냥 처음부터 순서대로 계속 뒤집으면 풀릴 것 같아서 그렇게 풀었더니 쉽게 풀렸다.

근데 다 풀어놓고 for문 중첩을 많이해서 i,j를 두번 써버리는 바람에 뭐가 잘못된지도 모르고 한참을 헤맸다. for문 너무 중첩하지 말고 항상 함수로 분리해서 쓰는 습관을 들이자.

코드

import sys


M,N = map(int,input().rstrip().split())
A = [list(map(int,input())) for i in range(M)]
B = [list(map(int,input())) for i in range(M)]

result = 0
check = False
    
for i in range(M-2):
    for j in range(N-2):

        if A[i][j] != B[i][j]:
           
            for a in range(i,i+3):
                for b in range(j,j+3):
                   
                    A[a][b] = 1-A[a][b]
            result+=1

for i in range(M):
    for j in range(N):
        if A[i][j] != B[i][j]:
            check = True

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

3 4
0000
0010
0000
1001
1011
1001
2