[Baekjoon] 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을 출력한다.

예제

Example 1:

Input: 
3 4
0000
0010
0000
1001
1011
1001
Output: 
2

조건

시간 제한 : 2초

메모리 제한 : 128 MB

풀이과정

내 풀이

N, M = list(map(int, input().split()))
#변환해야할 행렬
map_list = [list(map(int, list(input()))) for _ in range(N)]
#목표의 행렬
target_list = [list(map(int, list(input()))) for _ in range(N)]

# 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집어준다.
def change(start, arr):
    x, y = start
    for i in range(x,x+3):
        for j in range(y, y+3):
            arr[i][j] = 1-arr[i][j]
cnt = 0

# (0,0)에서부터 차례대로 뒤집을수있다면 뒤집고 카운트.
for i in range(N-2):
    for j in range(M-2):
        if map_list[i][j] != target_list[i][j]:
            cnt += 1
            change((i,j),map_list)

# 바꿀 수 있다면 카운트를 출력, 바꿀 수 없다면 -1을 출력.
if map_list == target_list:
    print(cnt)
else:
    print(-1)