[백준 BOJ / Python] 1080번 행렬

문제

0과 1로만 이루어진 행렬 A,B가 있다. 이때 행렬 A를 B로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제이다.
행렬 변환 연산은 3*3 부분 행렬에 있는 모든 원소를 0은 1로 1은 0으로 바꾸는 것이다.
만약 바꿀 수 없다면 -1를 출력한다.

풀이

• N*M 행렬을 모두 순회하면서 (i,j)값이 A와 B가 다른 경우,
  A의 (i,j)부터 3*3 부분행렬을 뒤집어 (i,j)값이 동일하도록 바꾸어 준다.
• 이때 (i,j)를 시작점으로 3*3 부분행렬을 뒤집어주는 이유는 
  앞의 이미 B와 동일한 부분은 건들지 않으면서 뒤의 다른 부분은 다시 뒤집을 수 있기 때문이다.
• 가능한 모든 부분행렬을 한번씩 살펴봄으로써 뒤집어야하는 최소 횟수를 구할 수 있다.

알고리즘

1. for문을 통해 3*3 영역을 뒤집을 수 있는 flip 함수를 정의한다.
2. 만약 A와 B의 (i,j)값이 다르다면 flip 하고, 뒤집은 횟수(cnt)를 증가시킨다.
3. A와 B가 같다면 뒤집은 횟수를 출력한다.
4. 끝까지 A와 B가 같지 않다면 -1을 출력한다.

Python 코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
a = [list(map(int,list(input().strip()))) for _ in range(n)]
b = [list(map(int,list(input().strip()))) for _ in range(n)]

def flip(x,y):
    for ii in range(3):
        for jj in range(3):
            # 0 <-> 1로 전환 시킴
            a[x+ii][y+jj] = 1 - a[x+ii][y+jj]
def sol():
    if a == b: # 처음에 같은 경우는 바로 0 return
        return 0

    cnt = 0
    for i in range(n-2):
        for j in range(m-2):
            if a[i][j] != b[i][j]: #만약 서로 다르면 a의 3x3을 전환시킴
                flip(i,j)
                cnt += 1

            if a == b:
                return cnt
    return -1

print(sol())

 

문제출처

1080번: 행렬