[백준] [그리디] 1080. 행렬 📍

1080. 행렬

1080번: 행렬

 

• 풀이
  • (0,0)은 (1,1)을 가운데로 낀 3x3 블럭이 아니면 아무도 값을 바꿀 수가 없다
  • (0,1)은 (1,2)을 가운데로 낀 3x3 블럭이 아니면 아무도 값을 바꿀 수가 없다
    • → 이런식으로 앞의 값들은 그 블럭이 지나고나면 손을 댈수가 없기 때문에 무조건 그 블록에서 바꿔야하는 것!
  • 해당 칸의 값이 목표 그래프와 다르다면 그 블럭은 블럭을 바꾸는 선택밖에 할 수가 없음
  • 해당 칸의 값이 목표 그래프와 같다면 그 블럭은 블럭을 바꾸지 않는 선택밖에 할 수가 없음 
    • → 그 위치에서 최선의 선택 (바꾼다 / 안바꾼다) 
    • → 그리디
  • 각각의 위치에서 최선을 다하고 끝냈는데 확인해보니 다르다? → 다른 방법이 없는 것이니까 -1

def change(x, y):
    for i in range(3):
        for j in range(3):
            if graphA[x+i][y+j] == 0:
                graphA[x+i][y+j] = 1
            elif graphA[x+i][y+j] == 1:
                graphA[x+i][y+j] = 0
    return


n, m = map(int, input().split())
graphA = []
graphB = []
for i in range(n):
    graphA.append(list(map(int, input().rstrip())))

for i in range(n):
    graphB.append(list(map(int, input().rstrip())))

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

for a, b in zip(graphA, graphB):
    if a != b:
        print(-1)
        exit()

print(cnt)