PS/백준
백준 / 그리디 / 1080번 / 행렬 / Python
KimMinJun
2022. 3. 12. 15:38
문제
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을
구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)
입력
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는
행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.
from sys import stdin
n, m = map(int, stdin.readline().split())
a = []
b = []
for _ in range(n):
a.append(list(map(int, list(input()))))
for _ in range(n):
b.append(list(map(int, list(input()))))
def toggle(i, j):
for x in range(i, i+3): # i부터 i+2까지
for y in range(j, j+3):
a[x][y] ^= 1 # xor, (0=>1, 1=>0)
cnt = 0
# 행과 열이 3보다 작고,
# 둘의 행렬이 다를경우 변환 불가
if(n < 3 or m < 3) and a != b:
cnt = -1
else:
for x in range(n-2):
for y in range(m-2):
if a[x][y] != b[x][y]:
toggle(x, y)
cnt += 1
if a != b:
cnt = -1
print(cnt)