[백준/파이썬] 1080 행렬

#문제링크

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

1080번: 행렬

#나의풀이

import sys

def reverse(x, y):
    for i in range(x,x+3):
        for j in range(y, y+3):
            first_matrix[i][j] = 1 - first_matrix[i][j]

if __name__=="__main__":
    N, M = map(int, sys.stdin.readline().split())
    first_matrix = [[0] * M for _ in range(N)]
    second_matrix = [[0] * M for _ in range(N)]
    count = 0
    flag = False

    for i in range(N):
        S = sys.stdin.readline().strip()
        for j in range(M):
            first_matrix[i][j] = int(S[j])
    for i in range(N):
        S = sys.stdin.readline().strip()
        for j in range(M):
            second_matrix[i][j] = int(S[j])

    for i in range(N-2):
        for j in range(M-2):
            if first_matrix[i][j] != second_matrix[i][j]:
                reverse(i, j)
                count += 1
            if first_matrix == second_matrix:
                break
        if first_matrix == second_matrix:
            break

    if first_matrix != second_matrix:
        print(-1)
    else:
        print(count)

#해설

그리디 문제라고 해서 골랐는데 왜 그리디인지 다른사람의 설명을 보고 이해했다.

주어진 문제에서는 숫자가 0과 1로 주어지는데 두 행렬을 비교하여 값이 다르면 무조건 뒤집어줘야 하기 때문에 그리디 문제로 분류된다라고 하셨다.

 

각 행렬을 첫번째와 두번째로 나누어 받고 뒤집는건 3x3이므로 각 행렬의 row, column을 -2씩 해서 for문을 돌려줬다.(혹시 이부분이 이해가 안된다면 직접 해보거나 스도쿠 문제를 풀어보세요)

이후 첫번째행렬의 값과 두번째행렬의 값이 다르면 reverse함수로 뒤집는다.

 

reverse 함수는 간단하게 2진수를 생각하면 되는데 0은 1이되야하고 1은 0이 되어야 하기때문에 1 - 값을 하면 충족하게 된다.

 

이후 두 행렬이 같다면 break문을 사용해서 빨리 끝내주었다