[Python][백준] 1080_행렬

https://www.acmicpc.net/problem/1080

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

---

방법이 쉽게 떠오르지 않아 다른 사람의 풀이를 참고했는데

greedy algorithm으로 풀이가 가능하다.

그런데 과연 어떻게 접근하는 것이 최적해일까?

 

[조건]

- 먼저, 두 행렬의 값이 다르면 무조건 해당 인덱스에서는 연산을 수행해야한다.

- i, j 인덱스보다 앞에 있는 행렬 값이 전부 일치한다면, 앞 부분에서는 연산을 수행해서는 안된다.

 

[풀이]

--> 두 행렬의 원소값이 같은지 여부를 저장하는 chk 배열을 생성

--> chk 행렬을 순회하며, chk[i][j] == 1이면 chk[i:i+3][j:j+3]의 값을 모두 변경

--> chk 행렬 순회가 끝났을 때 더 이상 chk 행렬의 원소값이 1인 경우가 없는지 확인

 

import sys

def func(i, j):
    for a in range(i, i+3):
       for b in range(j, j+3):
           chk[a][b] = 1 if chk[a][b] == 0 else 0

N, M = list(map(int, sys.stdin.readline().split()))

li1 = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
li2 = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
chk = [[0 if li1[i][j] == li2[i][j] else 1 for j in range(M)] for i in range(N)] # 같으면 0 다르면 1

ans = 0
for i in range(N-2):
    for j in range(M-2):
        if chk[i][j] == 1:
            func(i,j)
            ans+=1



sum = sum([sum(chk[i]) for i in range(N)])
ans = -1 if sum > 0 else ans

print(ans)