[🥈1 / 백준 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을 출력한다.

 

예제 입력 1 3 4 0000 0010 0000 1001 1011 1001	예제 출력 1 2
예제 입력 2 3 3 111 111 111 000 000 000	예제 출력 2 1
예제 입력 3 1 1 1 0	예제 출력 3 -1
예제 입력 4 18 3 001 100 100 000 011 010 100 100 010 010 010 110 101 101 000 110 000 110 001 100 011 000 100 010 011 100 101 101 010 001 010 010 111 110 111 001	예제 출력 4 7

 

풀이

 

N-3, M-3 부분까지만 순차적으로 탐색한다.

탐색중인 부분을 x, y라고 할 때, 만약 A[x][y] 와 B[x][y]가 다르다면 x, y 를 기준으로 3x3 칸을 뒤집는다.

이제 공간이 없어 더 이상 뒤집기를 할 수 없을 때 행렬 A와 B를 비교하여 같다면 뒤집기를 한 횟수를, 다르다면 -1을 출력한다.

 

구현은 어렵지 않지만 아이디어를 떠올리기 어려웠던 문제같다.

 

import sys
input = sys.stdin.readline

def flip(x,y):
    if x+3>n or y+3>m:
        return -1
    for i in range(x,x+3):
        for j in range(y,y+3):
            if board[i][j] == 0:
                board[i][j] = 1
            else:
                board[i][j] = 0

n,m = map(int,input().split())
board = [list(map(int,list(input().rstrip()))) for _ in range(n)]
ans = [list(map(int,list(input().rstrip()))) for _ in range(n)]

t = 0
for i in range(n-2):
    for j in range(m-2):
        if board[i][j] != ans[i][j]:
            t += 1
            flip(i,j)

print(t if board == ans else -1)