[백준] # 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을 출력한다.

 

 

IDEA

 

행렬의 맨 왼쪽 위부터 오른쪽 맨 아래까지 A와 B 원소 값을 비교하며 값이 다른 경우 행렬 3x3 크기 값을 모두 바꾼다.

 

 

 

CODE

# 1080. 행렬 - 실버2
n,m = map(int,input().split())

a = [list(map(int,input())) for _ in range(n)]
b = [list(map(int,input())) for _ in range(n)]
cnt = 0

def changeMatrix3x3(x,y):
    for i in range(3):
        for j in range(3):
            a[x+i][y+j] = 1 - a[x+i][y+j]

for i in range(n-2):
    for j in range(m-2):
        if a[i][j] != b[i][j]:
            changeMatrix3x3(i,j)
            cnt += 1
check = False
for i in range(n):
    for j in range(m):
        if a[i][j] != b[i][j]:
            check = True;
            break
    if check:
        break

if check:
    print(-1)
else:
    print(cnt)

 

사용 알고리즘

 

그리디

 

풀이 평

 

아이디어를 생각하기가 어려웠다.