[코테] 백준 그리디 1080번 문제

1080번 : 행렬

문제 링크

https://www.acmicpc.net/problem/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. 두 행렬을 입력받아서 한개의 값이 같으면 0, 다르면 1로 저장하는 별개의 배열을 만든다.
2. 3x3씩 오른쪽, 밑으로 이동하면서 전체를 바꾸고, 그 값을 저장 및 count + 1 한다.
3. 마지막 3x3을 변경했음에도 전체 배열의 값이 0이 안되면 -1을 한다.

N, M = map(int, input().split())
A = []
B = []
diff_arr = [[0 for j in range(M)] for i in range(N)]
count = 0

for i in range(N) : A.append(input())
for i in range(N) : B.append(input())
    
for i in range(N) :
    for j in range(M) :
        if A[i][j] != B[i][j] :
            diff_arr[i][j] = 1

for i in range(N-2) :
    try :
        idx = diff_arr[i].index(1)
        
        while idx <= M - 3 : 
            for ch_row in range(i, i+3) :
                for ch_col in range(idx, idx+3) :
                    diff_arr[ch_row][ch_col] = diff_arr[ch_row][ch_col] ^ 1
        
            count += 1
            idx = diff_arr[i].index(1)
        
    except : 
        continue

if sum([sum(i) for i in diff_arr]) != 0 : 
    print(-1)
else :
    print(count)