백준 그리디 알고리즘 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을 출력한다.

풀이

뒤집히는 부분이 부분행렬을 포함하는 3x3 행렬이기 때문에 행과 열의 앞부분만 바꿔주어도 밑에도 같이 바뀐다.

따라서 처음 반복문을 a-2, b-2만큼 돌아 다른 부분이 있으면 reverseList 함수를 호출한다.

reverseList함수에서는 인자로 받은 인덱스 +3까지 기준을 잡아 0은 1로 1은 0으로 수정하는데

나는 1에서 뺀 값에 절대값을 만드는것으로 구현했다.

모든 비교 밑 수정이 끝나고 반복문을 돌아 두개의 행렬이 다르다면 -1을 출력하고

같다면 뒤집은 count를 출력한다.

 

 

import sys
a, b = map(int,sys.stdin.readline().rstrip("\n").split())
listA = [list(map(int,sys.stdin.readline().rstrip("\n"))) for _ in range(0,a)]
listB = [list(map(int,sys.stdin.readline().rstrip("\n"))) for _ in range(0,a)]
count=0

def reverseList(t,s):
    global count
    count += 1
    for i in range(t,t+3):
        for j in range(s,s+3):
            listA[i][j] = abs(1-listA[i][j])


for i in range(0,a-2):
    for j in range(0,b-2):
        if(listA[i][j] != listB[i][j]):
            reverseList(i,j)

for i in range(0,a):
    for j in range(0,b):
        if(listA[i][j] != listB[i][j]):
            count = -1

print(count)