두 개의 N×M 크기 이진 행렬 A와 B가 주어졌다고 가정해 보겠습니다. 한 번의 연산에서 우리는 최소 2×2 이상의 크기를 가진 부분 행렬을 선택하고, 그 네 모서리에 위치한 요소들의 패리티(비트)를 반전시킬 수 있습니다. 목표는 이러한 연산을 원하는 만큼 수행했을 때 행렬 A를 행렬 B로 변환할 수 있는지 확인하는 것입니다.
예를 들어, 다음과 같은 입력이 주어진 경우를 살펴보겠습니다.
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 0 | 0 |
위 행렬의 왼쪽 위 2×2 부분 행렬에 연산을 한 번 적용하면 아래와 같이 변환됩니다.
이 경우 출력 결과는 True입니다. 왼쪽 위 2×2 정사각형 부분 행렬에 연산을 수행하면 두 번째 행렬을 얻을 수 있기 때문입니다.
해결 접근 방식
이 문제를 해결하기 위한 핵심 아이디어는 그리디(Greedy) 기법입니다. 각 내부 셀 (i, j)을 순서대로 검사하면서, 현재 값이 목표 행렬의 값과 다르다면 즉시 수정하는 것입니다.
셀 (i, j)의 값을 바꿔야 할 때, 우리는 (0, 0), (0, j), (i, 0), (i, j)를 모서리로 하는 2×2 부분 행렬에 연산을 적용하는 것과 동일한 효과를 냅니다. 즉, 네 개의 모서리 요소를 모두 XOR 연산으로 뒤집으면 됩니다. 이렇게 하면 대상 셀은 목표 값과 일치하게 되고, 이미 처리가 끝난 내부 영역에는 영향을 주지 않습니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- row := mat1의 행 개수
- column := mat1의 열 개수
- i를 1부터 row-1까지 순회하며:
- j를 1부터 column-1까지 순회하며:
- 만약 mat1[i][j]가 mat2[i][j]와 다르다면:
- mat1[i][j] := mat1[i][j] XOR 1
- mat1[0][0] := mat1[0][0] XOR 1
- mat1[0][j] := mat1[0][j] XOR 1
- mat1[i][0] := mat1[i][0] XOR 1
- 만약 mat1[i][j]가 mat2[i][j]와 다르다면:
- j를 1부터 column-1까지 순회하며:
- 모든 셀을 다시 순회하며 mat1과 mat2가 다른 셀이 하나라도 있다면 False를 반환하고, 모두 일치하면 True를 반환합니다.
예제 코드
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
def solve(mat1, mat2):
row = len(mat1)
column = len(mat1[0])
for i in range(1, row):
for j in range(1, column):
if mat1[i][j] != mat2[i][j]:
mat1[i][j] ^= 1
mat1[0][0] ^= 1
mat1[0][j] ^= 1
mat1[i][0] ^= 1
for i in range(row):
for j in range(column):
if mat1[i][j] != mat2[i][j]:
return False
return True
mat1 = [
[1, 0, 0],
[1, 0, 1],
[1, 0, 0]]
mat2 = [
[0, 1, 0],
[0, 1, 1],
[1, 0, 0]]
print(solve(mat1, mat2))입력
[
[1, 0, 0],
[1, 0, 1],
[1, 0, 0]],
[
[0, 1, 0],
[0, 1, 1],
[1, 0, 0]]출력
True
이 알고리즘의 시간 복잡도는 O(N×M)으로, 행렬의 모든 셀을 상수 시간 안에 한 번씩만 처리하면 되기 때문에 매우 효율적입니다.