[백준][1080] 행렬

• Problem Link : https://www.acmicpc.net/problem/1080

문제

• A, B 행렬이 주어질때 A 행렬을 B 행렬로 바꾸는데 필요한 연산 횟수의 최솟값
• 이 때 3x3 단위로만 행렬의 원소를 뒤집을 수 있다.

입력

• 첫째 줄, 행렬의 크기 N, M
• 다음 줄, N개의 줄에 행렬 A
• 그 다음 줄, N개의 줄에 행렬 B

출력

• 첫째 줄에 연산 횟수 출력, 바꿀 수 없다면 -1 출력

풀이

해당 행렬이 1과 0으로만 이루어진 행렬이고, A와 B가 완전히 똑같아야 하므로 결국 모든 원소를 비교해 나가면서 뒤집어야한다.

모든 원소를 비교해나가면서 만약 다른 원소가 있다면 그 원소를 기준으로 3x3 행렬을 뒤집어야 하고 해당 반복 과정이 끝났을때 A와 B가 같아졌다면 뒤집은 횟수를 출력, 만약 반복문이 끝났는데 A와 B가 다르다면 A를 뒤집어도 B를 만들 수 없는 것이기 때문에 -1을 출력한다.

• 3x3으로 뒤집기 때문에 n행, m열까지 진행하면 indext out of range가 발생하기 때문에 반복은 맨 뒤의 2개의 행과 열을 제외하고 진행한다.

결국 이 문제는 원소를 비교하면서 같지 않으면 한 쪽 원소를 뒤집는데 이 때 3x3 사이즈로 뒤집기만 하면 되는 간단한 문제였다.

코드

import sys

input = sys.stdin.readline


def change(A, i, j):
    for x in range(i, i + 3):
        for y in range(j, j + 3):
            A[x][y] = "0" if A[x][y] == "1" else "1"
    return A


n, m = map(int, input().split())
A = []
B = []
for _ in range(n):
    A.append(list(map(str, input()[:-1])))
for _ in range(n):
    B.append(list(map(str, input()[:-1])))

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

print(cnt if A == B else -1)