[Python] Baekjoon - 1080. 행렬

백준 1080번 행렬 문제는 0과 1로만 이루어진 두 개의 3x3 행렬을 최소 몇 번의 뒤집는 연산으로 같게 만드는지 최소 횟수를 구하는 문제다. 그리디 알고리즘을 이용해 해결할 수 있으며 난이도는 실버 2이다.

 

백준 1080번 행렬 문제 정보

알고리즘 분류

• 그리디 알고리즘

난이도

• 실버 2

 

행렬 문제 요약

• 0과 1로만 이루어진 MxN 행렬 A와 B
• 연산: 행렬의 3x3만큼을 뒤집는 것 (0은 1로, 1은 0으로)
• A를 B로 만들기 위한 최소 연산 횟수 구하기

 

문제 풀이 방법

과정

• 뒤집기 연산이기 때문에 연산의 '순서'는 상관없으며, 같은 곳을 두 번 이상 뒤집을 필요 없음
  • 따라서 각 칸에대해 연산을 수행할지 말지 정하면 됨
• 왼쪽 위부터 순서대로 연산 필요 여부를 판단한다면, 3x3중 왼쪽 위칸만 확인하고 B랑 다르면 연산 수행하면 됨
  • 따라서 (M-2)x(N-2)만큼의 행렬만 확인하면서 연산 필요 여부 판단
• 모든 연산을 수행한 뒤, 남은 부분도 B와 일치하면 연산 횟수를 반환하고, 일치하지 않으면 불가능한 경우이므로 -1 반환

풀이

• reverse(mtrx, r, c): 행렬 mtrx에서 왼쪽 위칸이 (r,c)인 3x3 행렬에 연산을 수행하는 함수
• 연산을 수행할 수 없는 input (행렬의 행 또는 열의 길이가 3보다 작음) 예외 처리

 

코드

import sys


# 행렬 mtrx에서 왼쪽 위칸이 (r,c)인 3x3 행렬에 연산을 수행하는 함수
def reverse(mtrx, r, c):
    global H, W
    d = [0, 1, 2]
    for i in range(3):
        for j in range(3):
            hereR, hereC = r + d[i], c + d[j]
            if mtrx[hereR][hereC] == '0':
                mtrx[hereR][hereC] = '1'
            else:
                mtrx[hereR][hereC] = '0'


def getMinOperation():
    global H, W, start, dest
    reverseCnt = 0

    if H >= 3 and W >= 3:
        # 각 위치에 대해 연산을 수행해야하는지, 아닌지를 체크
        for r in range(H-2):
            for c in range(W-2):
                # 왼쪽 상단이 다르면 무조건 뒤집기
                if start[r][c] != dest[r][c]:
                    reverse(start, r, c)
                    reverseCnt += 1

    # 완성된 행렬과 목표행렬이 같으면 연산 횟수 반환, 다르면 -1 반환
    if start == dest:
        return reverseCnt
    else:
        return -1


if __name__ == '__main__':
    H, W = map(int, input().split())
    start, dest = [], []
    for _ in range(H):
        start.append([*sys.stdin.readline().strip()])
    for _ in range(H):
        dest.append([*sys.stdin.readline().strip()])

    print(getMinOperation())