[python] 백준 - 1080(행렬)

실버1 문제이며, 제한 시간은 2초이다.

문제

해결 과정

우선 처음 딱 봤을 때 어떻게 풀지? 라는 생각이 제일 먼저 들었다. 하지만 문제 유형을 이미 알기에 그리디라고 생각하고 접근해보니 그냥 행렬 a와 b의 같은 자리의 값이 다르면 연산을 수행하면 되지 않을까? 생각했다. 따라서 뒤집을 자리가 행렬의 범위를 벗어나지 않는 선에서 값이 다르면 뒤집는 연산을 수행하도록 코드를 작성했다.

풀이

def flip(x, y):
  for i in range(3):
    for j in range(3):
      if mat_a[x + i][y + j] == 0:
        mat_a[x + i][y + j] = 1
      else:
        mat_a[x + i][y + j] = 0
          
n, m = map(int, input().split())
mat_a = []
mat_b = []

for _ in range(n):
  mat_a.append(list(map(int, input())))
for _ in range(n):
  mat_b.append(list(map(int, input())))

answer = 0
for x in range(n):
  for y in range(m):
    if mat_a[x][y] != mat_b[x][y]:
      if x + 2 < n and y + 2 < m:
        flip(x, y)
        answer += 1

if mat_a != mat_b:
  print(-1)
else:
  print(answer)

정당성 분석

제출해보니 정답이었고, 다시 코드를 보며 생각을 해봤다. 이 문제의 그리디적인 요소는 a와 b의 같은 위치의 값이 다르면 연산을 수행한다는 점이다.

이 동작이 성립할 수 있는 이유는 그 위치의 값이 달라서 연산을 수행한 경우, 그 이후에 어디서 연산을 수행하던 그 위치의 값은 변하지 않기 때문이다. (3 * 3은 현재 위치를 기준으로 x + 2, y + 2까지 뒤집는다)