[Python] 16711번 Erasing Matrix

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

---

 

25/08/28

 

 

이전에 비슷한 걸 풀었는데, 거기서 좀더 응용하면 문제를 해결할 수 있다.

2023.03.14 - [알고리즘/백준 문제 풀이] - [Python] 9718번 Matrix Transformation

[Python] 9718번 Matrix Transformation

 

---

 

문제 접근 방식:

 

 

하나의 보드를 체스판처럼 흰색 칸과 검은색 칸으로 나누자.

 

그러면 인접한 두 수에 $k$를 더하고 빼는 작업은 흰색 칸에 놓여진 숫자의 합과 검은색 칸에 놓여진 숫자의 합 모두에 $k$를 더하고 빼는 작업과 같다.

 

따라서 이 시행을 해서 보드에 놓인 모든 수를 0으로 만들 수 있냐의 여부는, 흰색 칸과 검은색 칸에 놓인 숫자들의 합이 서로 같은지 다른지의 여부를 묻는 것과 동일하다.

 

이를 통해 불가능 여부를 판별한다.

 

가능 하다면 그 방법을 이제 출력해야하는데, 이는 다음과 같은 방법으로 구성했다.

 

먼저, 보드판을 전부 훑는 경로를 하나 구성한다. 나의 경우, 오른쪽으로 쭉 갔다가 아래로 한칸, 다시 왼쪽으로 쭉 갔다가 아래로 한칸, 다시 오른쪽으로.... 그렇게 뱀처럼 꼬불꼬불 이어져있는 경로를 구성했다.

 

이후 경로에 놓인 수들을 순서대로 $a_1, a_2, a_3, \dots$라고 했을 때, $a_i$과 $a_{i+1}$을 비교한다.

 

만약 $a_i$가 작다면 $a_i$와 $a_{i+1}$에 모두 $a_i$를 빼줘서 $a_i$를 $0$으로 만들어준다.

 

만약 $a_i$가 크다면 $a_{i+1}$과 $a_{i+2}$에 모두 $a_i$와 $a_{i+1}$의 차이만큼 더해준 뒤, $a_i$와 $a_{i+1}$에 모두 $a_i$만큼을 빼줘서 $a_i$와 $a_{i+1}$ 모두 $0$으로 만들어준다.

 

이를 반복하면 방법을 구성할 수 있다.

---

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

# 16711번 Erasing Matrix
# 불변량 찾기, 해 구성하기
import sys
input = sys.stdin.readline

# [-] is_inside
def is_inside(r, c):
    return 0 <= r < N and 0 <= c < M

# [-] 입력부
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

# [-] chain 구성
dr, dc = [0, 1, 0, 1], [1, 0, -1, 0]
r, c = 0, 0
chain = [(0, 0)]
idx = 0
while len(chain) < N*M:
    nr, nc = r+dr[idx], c+dc[idx]
    if idx & 1:
        idx = (idx+1)%4
    if is_inside(nr, nc):
        chain.append((nr, nc))
        r, c = nr, nc
    else:
        idx = (idx+1)%4

# [-] 흑/백 합 조건 따지기
black, white = 0, 0
for r in range(N):
    for c in range(M):
        if (r+c)%2 == 0:
            black += matrix[r][c]
        else:
            white += matrix[r][c]
if black != white:
    print(-1)
# [-] 실제 구성
else:
    ans = []
    for i in range(len(chain)-1):
        r1, c1 = chain[i]
        r2, c2 = chain[i+1]
        a, b = matrix[r1][c1], matrix[r2][c2]
        if a == 0:
            continue
        if a <= b:
            matrix[r1][c1] -= a
            matrix[r2][c2] -= a
            ans.append((r1+1, c1+1, r2+1, c2+1, -a))
        else:
            r3, c3 = chain[i+2]
            matrix[r2][c2] += (a-b)
            matrix[r3][c3] += (a-b)
            ans.append((r2+1, c2+1, r3+1, c3+1, a-b))
            matrix[r1][c1] -= a
            matrix[r2][c2] -= a
            ans.append((r1+1, c1+1, r2+1, c2+1, -a))
    print(len(ans))
    for row in ans:
        print(*row)