[백준] 1080 행렬

📌문제 링크

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

💡 문제 풀이

일단 문제를 보고 나서 간단하게 이중반복을 사용해서 A의 원소와 B의 원소가 다르면 3x3만큼 뒤집는 방법으로 풀고 나서 나오는 답을 보고 방법을 수정해 나갈 생각이었는데, 그냥 이 방법 그대로 정답이 나와서 당황했다...

왜 이대로 정답이지? 어떻게 [i][j]를 3x3행렬의 가장 왼쪽 위 원소로 두고 뒤집는게 제일 최소일 수가 있지..? 하고 다른 블로그를 찾아봤다.

참고 블로그

뒤집는 연산의 특성상 2번 이상 뒤집는 것은 의미가 없습니다. 2번 뒤집으면 원래대로 돌아오고, 3번 뒤집는 것은 1번 뒤집는 것과 같습니다.
이때 최적의 선택은 "반드시 뒤집어야 하는 칸을 뒤집되, 뒤집는 횟수를 최소화하는 것" 입니다. 즉, 이미 뒤집은 칸을 2번이나 3번 뒤집지 않습니다.

이 설명을 보고 나서 왜 이 방법이 제일 최적인지, 왜 이 문제가 그리디인지 이해가 갔다.
A의 원소를 왼쪽 위부터 하나씩 살피면서 B와 다르면 뒤집고, 이미 한 번 뒤집었으므로 그 원소는 다시 뒤집지 않도록 A[i][j]를 3x3 행렬의 가장 왼쪽 위 원소로 생각하고 뒤집으면 최적의 해가 나오는 거였다.

📋코드

# 1080 행렬
n, m = map(int, input().split())
A = []
B = []
count = 0

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

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

# 행렬이 같으면 0 출력
# 이 때, 행렬이 3x3보다 작아도 0을 출력하게 됨
if A == B:
    print(0)
    exit()


# 3x3만큼 뒤집음
def invert(i, j):
    for k in range(3):
        for l in range(3):
            A[i + k][j + l] += 1
            A[i + k][j + l] %= 2


# 3x3만큼 뒤집을 수 있는 범위 안에서 반복
# A의 원소와 B의 원소가 다르면 거기서부터 3x3만큼 뒤집음
for i in range(n-2):
    for j in range(m-2):
        if A[i][j] != B[i][j]:
            invert(i, j)
            count += 1

if A == B:
    print(count)
else:
    print(-1)