[Python 3] BOJ - 1080 "행렬"

 # 문제 링크 : https://www.acmicpc.net/problem/1080

1080번: 행렬

 # 풀이 : 

 개인적으로 이 문제는 그리디 알고리즘을 생각할 수 있는지가 핵심이라고 생각한다.

<그림 1. N = 3, M = 4인 행렬의 경우>

 위 그림1에서 빨간색 부분은 뒤집는 지점이고, 파란색 부분은 빨간색 부분을 뒤집었을 때, 영향을 받아 같이 뒤집어지는 지점을 의미한다. 따라서 0행 0열에서 뒤집게 되면 0행 1열, 0헹 2열, 1행 0열, 1행 1열, 1행 2열, 2행 0열, 2행 1열, 2행 2열이 같이 뒤집어진다.

<그림 2. N = 3, M = 4인 행렬의 경우>

 위 그림2는 그림1의 과정 이후 0행 1열에서 뒤집은 경우이다. 마찬가지로 0행 1열에서 뒤집었으므로 0행 1열은 그림상에서 빨간색으로 나타내고 있다. 그런데, 그림1의 파란색 부분과 그림 2의 파란색 부분 중 공통되는 부분이 있다. 현재 행렬의 원소는 0과 1의 두가지 상태만을 가질 수 있으므로, 두 번 뒤집혔다면 원래의 원소로 돌아갔다는 뜻이다.

 그러나, 그림 1의 빨간색 부분과 그림 2의 빨간색 부분, 그림 1과 그림 2에서 파란색이었지만 겹치지 않은 부분은 상태가 바뀌었다고 할 수 있다.

<그림 3. N = 4, M = 4인 행렬의 경우>

 위 그림1과 그림2에서 1행 0열은 자신의 의도와는 원치 않게 상태가 바뀌게 되었다. 그러나, 행렬의 크기가 4X4인 그림 3처럼 된다고 가정할때, 1행 0열은 이전의 0행 0열에 의해 바뀐 상태를 또다시 바꿀 수 있는 선택이 주어지므로, 앞서 선택한 결과에 바뀜에도 불구하고, 행렬 B와 다르다면 그 시작점은 바꿔주면 이후에는 그 위치의 상태를 변경할 수 없다. 따라서 각 위치가 3 * 3의 부분 사각형의 범위 안에 있을 때, 행렬 B와 비교했을 때 다르다면 뒤집고, 같다면 그냥 넘어가면 되므로 다른 부분이 바뀜과 상관없이 그 위치가 같은지 다른지에 따라 뒤집거나 그렇지 않으므로 그리디 알고리즘의 방법을 적용하면 문제의 정답을 구할 수 있다.

 

 # 코드

import sys

# 입력부
n,m = map(int, sys.stdin.readline().split())
a = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
b = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ans = 0
flag = True

# flip : (x, y)에서 시작하여 3*3의 부분 사각형을 뒤집는 함수
def flip(x,y):
    for i in range(x - 1, x + 2):
        for j in range(y - 1, y + 2):
            if a[i][j] == '1':
                a[i][j] = '0'
            else:
                a[i][j] = '1'

# (i, j)에서 시작하여 3*3의 부분 사각형의 범위에 있다면
for i in range(n - 2):
    for j in range(m - 2):
        # 만약 B와 다르다면 뒤집고 연산 횟수를 증가시킨다
        if a[i][j] != b[i][j]:
            ans += 1
            flip(i + 1,j + 1)

# 만일 A와 B가 같지 않다면 더이상 뒤집을 수 없으므로 불가능한 경우이다
for i in range(n):
    for j in range(m):
        if a[i][j] != b[i][j]:
            flag = False

# 불가능한지, 가능한지에 따라 정답출력
if flag == True:
    print(ans)
else:
    print(-1)