문제
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)
입력
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.
코드
n, m = map(int, input().split())
matrix_a = []
matrix_b = []
for i in range(n):
matrix_a.append(list(input()))
for i in range(n):
matrix_b.append(list(input()))
cnt = 0
if n >= 3 and m >= 3:
for i in range(n-2):
for j in range(m-2):
if matrix_a[i][j] != matrix_b[i][j]:
# 3X3 뒤집기
for p in range(3):
for q in range(3):
if matrix_a[i+p][j+q] == '0':
matrix_a[i+p][j+q] = '1'
else:
matrix_a[i+p][j+q] = '0'
cnt += 1
for i in range(n):
for j in range(m):
if matrix_a[i][j] != matrix_b[i][j]:
cnt = -1
print(cnt)
처음에
1 1
1
1
이 경우를 고려하지 않고 배열의 크기가 3X3보다 작다면 무조건 -1을 리턴하게 했다. 생각해보니 배열의 크기가 3X3보다 작더라도 애초에 주어진 배열이 같은 경우 뒤집을 필요가 없으므로 답은 0이다.
'문제풀이 > Greedy' 카테고리의 다른 글
[Python/파이썬] 백준 6137번 문자열 생성 (2) | 2023.11.27 |
---|---|
[Python/파이썬] 백준 9576번 책 나눠주기 (1) | 2023.11.14 |
[Python/파이썬] 백준 13164번 행복 유치원 (1) | 2023.10.04 |
[Python/파이썬] 백준 2170번 선 긋기 (0) | 2023.09.28 |
[Python/파이썬] 백준 8980번 택배 (0) | 2023.09.07 |