[Python] 9718번 Matrix Transformation

https://www.acmicpc.net/problem/9718

9718번: Matrix Transformation

---

 

23/03/14

 

 

불변량의 개념을 숙지한 상태라면 쉽게 접근할 수 있는 문제이다.

 

만약 이 문제를 크기 제한($2 \leq R \leq 30$)만 보고 브루트포스나 그리디적으로 직접 시뮬레이션 돌려가며 구현할 생각을 했다면 시간초과가 날 것이다.

---

 

문제 접근 방식:

 

 

먼저, 어떤 변환을 했을 때에도 항상 변하지 않는 값이 있는지 찾아보자.

 

한 가지 관찰할 수 있는 사실은, 행렬을 체스판처럼 검은색과 흰색으로 칠한 뒤에, 두 인접한 칸을 잡으면, 그 두 칸은 항상 검은 칸과 흰색 칸이라는 사실을 알 수 있다.

 

다시 말해, $(i, j)$칸이 있을 때, $(i+j) \ mod \ 2 \ = 0$이 되는 칸을 흰색 칸, $(i+j) \ mod \ 2 \ = 1$이 되는 칸을 검은 칸이라고 하면, 임의의 두 인접한 칸은 항상 흰색 칸과 검은 칸이 된다는 사실을 알 수 있다.

 

때문에 우리가 하는 행동은, 흰색 칸 하나와 검은 칸 하나 각각에 $1$을 더하거나 빼는 것과 같다.

 

 

이를 통해 알 수 있는 것은, (흰색 칸 숫자의 총합) - (검은색 칸 숫자의 총합)은 행동 이후에도 항상 변하지 않는다는 사실이다.

 

문제에서는 행동의 반복을 통해 영행렬을 만들 수 있는지의 여부를 묻고있다.

 

따라서, 초기 상태에서 영행렬과 같이 (흰색 칸 숫자의 총합) - (검은 색 칸 숫자의 총합) $=$ $0$이 되는지의 여부만 체크해주면 해결할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 9718번 Matrix Transformation
# 수학, 애드혹, 불변량
'''
접근 방법:
(i, j)칸이 있을 때, 이 칸의 위치를 i+j라고 하자.
그러면 i+j가 홀수가 되는 칸과 짝수가 되는 칸으로 임의의 칸을 분류할 수 있다.
두 인접한 칸을 잡으면, 항상 그 두 칸은 i+j가 홀수가 되는 칸과
짝수가 되는 칸이므로, 그 두 칸에 모두 1을 빼거나 더해도,
(홀수칸 숫자의 총합) - (짝수칸 숫자의 총합)은 항상 변하지 않는다.
따라서, 초기 상태에서 (홀수칸 숫자의 총합) - (짝수칸 숫자의 총합)이
0이 되는지만 판단해주면 영행렬을 만들 수 있는지 판단할 수 있다.
'''
import sys
input = sys.stdin.readline

def matrix_can_change_into_zero_matrix(matrix, row, col):  # 행렬과 행렬 크기를 인자로 받음.
    odd_sum = 0
    even_sum = 0
    for r in range(row):
        for c in range(col):
            if (r+c)%2 == 0:
                even_sum += matrix[r][c]
            else:
                odd_sum += matrix[r][c]
    if odd_sum - even_sum == 0:
        return True
    else:
        return False
                                
T = int(input())  # 테스트 케이스 개수
for _ in range(T):
    row, col = map(int, input().rstrip().split())
    matrix = [list(map(int, input().rstrip().split())) for _ in range(row)]
    print('YES' if matrix_can_change_into_zero_matrix(matrix, row, col) else 'NO')