BOJ: 1080

Posted on In

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 $\rightarrow$ 1, 1 $\rightarrow$ 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

Solution

입력 구현

1
2
3
4
5
6
7
8
9
10
11
12
import sys
read = sys.stdin.readline

N, M = map(int, read().split())
A = [[] for _ in range(N)]
B = [[] for _ in range(N)]

for i in range(N):
  A[i] = list(read().rstrip())
  
for i in range(N):
  B[i] = list(read().rstrip())

행렬 원소 뒤집는 함수 구현

1
2
3
4
5
6
7
def cal(mat, x, y):
  for i in range(3):
    for j in range(3):
      if mat[x + i][y + j] == '1':
        mat[x + i][y + j] = '0'
      else:
        mat[x + i][y + j] = '1'

우선 순위 배정 및 원소 뒤집기

1
2
3
4
5
6
7
cnt = 0

for i in range(N - 2):
  for j in range(M - 2):
    if A[i][j] != B[i][j]:
      cal(A, i, j)
      cnt += 1
  • 좌측 상단에서 우측 하단으로 훑으며 A, B의 i, j에서 원소가 다를 경우 3$\times$3만큼 원소를 뒤집는다.
  • 또한 해당 작업을 행할 때 출력을 위해 cnt 변수를 1만큼 더한다.

예외 처리

1
2
3
4
5
6
7
8
9
10
11
12
status = True

for i in range(N):
  for j in range(M):
    if A[i][j] != B[i][j]:
      status = False
      break

if status:
  print(cnt)
else:
  print(-1)
  • 대부분의 원소가 다를 경우 뒤집혔지만 우측 하단의 2$\times$2의 원소의 비교는 이루어지지 않았다.
  • 따라서 A와 B의 원소를 재검사하고 한 원소라도 다를 시 불가능을 의미하는 -1을, 가능할 경우 연산의 횟수인 cnt를 출력한다.