[백준 - Python] 1080. 행렬 (그리디)

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

1080번: 행렬

 

코드

import sys

n, m = map(int, sys.stdin.readline().split())
a = []
b = []
for _ in range(n):
    a.append([int(ch) for ch in sys.stdin.readline().strip()])
for _ in range(n):
    b.append([int(ch) for ch in sys.stdin.readline().strip()])

def flip(r, c):
    for i in range(r, r+3):
        for j in range(c, c+3):
            if a[i][j] == 1:
                a[i][j] = 0
            else:
                a[i][j] = 1

cnt = 0
for i in range(n-2):  # range(-1) 에 대한 처리는 ??
    for j in range(m-2):
        if a[i][j] != b[i][j]:
            flip(i, j)
            cnt += 1

print(cnt if a == b else -1)

 

문제 아이디어도 떠올리지 못했다.

다른 분들의 풀이를 참고했다.

 

행렬 A을 3x3 부분 행렬로 뒤집기 연산을 수행해 행렬 B로 만들려고 할 때

필요한 연산의 횟수의 최솟값을 구하는 문제였다.

 

행렬 A의 왼쪽 위부터 부분 행렬로 훑어가며,

부분 행렬의 왼쪽 위의 요소값이 행렬 B와 다르면 연산을 수행한다.

 

행렬 A를 훑으면서 가능한 연산이 전부 수행된 후에

행렬 B와 다르면 -1을 출력하고 같다면 행렬 B로 바꾸는 것이 가능하다는 것은 이해가 된다.

하지만 왜 이렇게 연산을 수행하는 것이

바꾸는데 필요한 연산 횟수의 최솟값이 될 수 있는지가 아직 완전하게 이해가 안됐다.

 

코드 면에서 배울 점은,

이차원 배열을 기반의 연산이거나 연산 자체가 복잡한 연산일 경우에

연산을 함수로 독립적으로 빼서 구현하면 코드가 간결해 진다는 점이다.