백준 1080 행렬

import sys

n,m=map(int,sys.stdin.readline().split())
graphA=[list(map(int,sys.stdin.readline().rstrip()))for i in range(n)]
graphB=[list(map(int,sys.stdin.readline().rstrip()))for i in range(n)]


def display_graph():
    for i in graphA:
        print(i)
    print()

def change_graph(tempGraph,tempN,tempM):
    for i in range(tempN,tempN+3):
        for j in range(tempM,tempM+3):
            if tempGraph[i][j]==0:
                tempGraph[i][j]=1
            else:
                tempGraph[i][j]=0

def is_eqaul_graph(tempN,tempM):
    for i in range(tempN,tempN+3):
        for j in range(tempM,tempM+3):
            if graphA[i][j]!=graphB[i][j]:
                return 0
    return 1

def is_total_eqaul():
    for i in range(n):
        for j in range(m):
            if graphA[i][j]!=graphB[i][j]:
                return 0
    return 1

count=0
for i in range(n-2):
    for j in range(m-2):
        if graphA[i][j]!=graphB[i][j]:
            change_graph(graphA,i,j)
            count+=1

if is_total_eqaul()==1:
    print(count)
else:
    print(-1)

이 문제도 그리디로 풀수있는 문제이다.

​

한번에 3X3 범위에 해당하는 칸의 값을 변경할수 있는데, 몇번의 변경으로 A 행렬에서 B 행렬로 바꿀수 있나를 물어보는 문제이다.

​

3 4

0000

0010

0000

1001

1011

1001

0000

0010

0000

A 행렬

​

1001

1011

1001

B 행렬이라 했을때

몇번 만에 바꿀수있을까.

​

먼저 A행렬을 3X3 으로 나눈다면 두개의 영역이 있다.

000 000

001 이 부분과 010

000 000

​

으로 나뉘는데 각 영역의 첫번째 값을 B와 비교해서 같으면 그 영역을 전체 바꾸고 아니면 안바꾸는 방식으로 한다.

그리디로 풀기떄문에 각영역의 맨 왼쪽 위는 바뀌거나 안바뀌거나한뒤 넘어가게되면 이제 고정이되기에 다시는 바뀔일이 없기 때문이다.