문제 링크

https://www.acmicpc.net/problem/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을 출력한다.

문제 풀이

행렬은 3×3크기씩만 뒤집을 수 있으므로, 좌표 (0,0)부터 차례대로 (그리디하게) 행렬을 비교해나가면 바꿀 수 있는지 없는지 판별이 가능하다.

-> 똑같은 위치를 두 번 뒤집으면 똑같아지기 때문에 영향을 미칠 수 있는 건 같은 위치를 한번만 뒤집는것

맞은 코드

n, m = map(int, input().split())
beforeMatrix = [[] * m for _ in range(n)]
afterMatrix = [[] * m for _ in range(n)]
ans = 0

def changeMatrix(x, y):
  for i in range(y, y+3):
    for j in range(x, x+3):
      if beforeMatrix[i][j] == 0:
        beforeMatrix[i][j] = 1
      elif beforeMatrix[i][j] == 1:
        beforeMatrix[i][j] = 0

for i in range(n):
  temps = input()
  for temp in temps:
    beforeMatrix[i].append(int(temp))
    
for i in range(n):
  temps = input()
  for temp in temps:
    afterMatrix[i].append(int(temp))

for i in range(n):
  for j in range(m):
    if i <= n-3 and j <= m-3 and beforeMatrix[i][j] != afterMatrix[i][j]:
      changeMatrix(j, i)
      ans += 1

if beforeMatrix != afterMatrix:
  ans = -1

print(ans)