[Python] 백준 1080번 - 행렬 (실버 1)

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

1080번: 행렬

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 그리디 알고리즘

 

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

---

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = []
b = []
for i in range(n):
    a.append(list(input().rstrip()))
    
for i in range(n):
    b.append(list(input().rstrip()))

cnt = 0

if n >= 3 and m >= 3:
    for i in range(n-2):
        for j in range(m-2):
            if int(a[i][j]) != int(b[i][j]):
                for x in range(i, i+3):
                    for y in range(j, j+3):
                        a[x][y] = 1-int(a[x][y])
                        
                cnt += 1
                
for i in range(n):
    for j in range(m):
        if int(a[i][j]) != int(b[i][j]):
            print(-1)
            exit()
            
print(cnt)

n과 m이 3 이상일 때만 3x3비교를 할 수 있기 때문에 한번 걸러주었다.

 

마지막에 원본과 결과 비교를 맨 밑에서 하는 이유가

 

1 1
1
0
결과: -1

1 1
1
1
결과: 0

위와 같은 반례가 존재하기 때문이다.

 

위의 반례는 3x3이 안되기 때문에 변경이 불가능하여 -1을 출력하지만

 

아래의 반례는 변경이 불가능하나 동일한 행렬이기 때문에 0을 출력한 것이다.