[백준] 1080 - 행렬

문제

백준 1080번 행렬

 

알고리즘

그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 최적의 해를 구할 때, 선택 후 미칠 영향을 고려하지 않고 그 순간에 최이라고 생각될 때 선택해 나가는 방식으로 전체 문제의 최적의 해를 도출하는 방식이다.

그리디 알고리즘을 사용하기 위해서는 다음 두 조건을 충족해야 한다.

1. 최적 부분 구조(Optimal Substructure)
   전체 문제의 최적해를 부분 문제의 최적해로 구성할 수 있는 경우이다. 전체 문제를 작은 부분 문제로 나누어 각각의 해를 구해 조합했을 때의 값이 전체 문제의 최적해와 같다는 것이다.
2. 탐욕 선택 속성(Greedy Choice Property)
   각 단계에서의 최선의 선택이 전체 문제의 최적 해를 가져올 수 있다는 것을 의미한다. 

그리디 알고리즘은 각 단계에서 이전 선택과 이후 선택에 대한 고려 없이 현재 가장 우선이 되는 선택을 해나가는 것이다.

 

 

문제 풀이

이 문제는 A 배열을 B 배열과 같게 만들기 위해 3x3 크기로 0과 1을 뒤집는다면 몇 번 뒤집어야 하는지를 구하는 문제이다. 

어느 위치에서 어떤 순서로 뒤집어야 할지 모든 경우의 수를 탐색하는 브루트포스 탐색을 초기에 생각했으나, 경우의 수가 매우 많고 문제에서 요구하는 것 이상으로 복잡한 풀이를 하게 될 것이라 생각했다. 

모든 A의 값을 B와 동일하게 만들어야 하므로, [0,0]부터 [N-1,M-1]위치까지 한 칸을 범위로 순서대로 확인하는 것이 단순하게 풀이할 수 있을 것이라고 생각했다.

 

해당 풀이를 적용한다면 그리디 알고리즘에서 요구하는 두 가지 조건을 모두 충족한다.

1. 특정 위치 [i,j]의 값을 변경하는 것은 현재 위치의 문제를 해결하고, 이후와 이전 행렬에 독립적으로 적용된다. 따라서 3X3 범위의 각 위치에서의 선택이 최종해를 구성한다고 볼 수 있다.
2. 뒤집기를 미루고 다른 값을 미리 뒤집는 것이 최종해를 줄이는 데 기여하지 않기 때문에 순서대로 확인하는 것은 최종해 도출에 영향을 주지 않는다. 따라서 현재 위치의 선택이 전체 문제의 최적의 선택을 구성한다고 볼 수 있다.

따라서 이 문제에서 그리디 알고리즘을 적용할 수 있다.

 

한 코딩 테스트 책에서, 코딩 테스트에서 어떤 알고리즘을 적용해야 하는지 떠오르지 않거나 모든 경우를 탐색해야 할 것 같지만 브루트포스 알고리즘을 사용하기에는 복잡하다면, 그리디 알고리즘이 해결책이 될 수도 있다고 설명한다.

 

코드

import sys

input = sys.stdin.readline

n,m=map(int,input().split(' '))
A=[list(map(int,input().rstrip())) for _ in range(n)]
B=[list(map(int,input().rstrip())) for _ in range(n)]
ans=0

def flip(x,y):
  for i in range(x, x+3):
    for j in range(y, y+3):
        A[i][j]=(A[i][j]+1)%2

def is_same():
  for i in range(n):
    for j in range(m):
      if A[i][j]!=B[i][j]:
        return False
  return True

# n과 m이 3보다 작아도, A와 B가 이미 같다면, 뒤집을 필요가 없다.
if (n<3 or m<3) and not is_same():
  ans=-1
else:
  # n-3이 아니라 n-2인 이유는 i 위치를 포함하기 때문이다
  for i in range(n-2):
    for j in range(m-2):
      if A[i][j]!=B[i][j]:
        flip(i,j)
        ans+=1
  if not is_same():
    ans=-1
  
print(ans)