본문 바로가기

Problem Solving/문제풀이

[BOJ] 16711 Erasing Matrix

문제 링크: [BOJ 16711](https://www.acmicpc.net/problem/16711)

문제 요약

격자가 있다. 격자에서 인접한 두 수를 골라 임의의 수를 더할 수 있다. 격자 안의 수가 항상 음수가 되지 않게 하면서 최종적으로 모든 수가 0이 되게 하는 방법을 찾아라.

풀이

일단 가장 먼저 생각해봐야 할 점은 -1을 찍을 조건이다. 이런 식으로 격자에서 인접한 두 수를 고려하는 문제는 특성상 체스판처럼 색칠하면 이분 그래프 구조가 나오는데, 이를 활용해 볼 수 있다. 인접한 두 수에 어떤 수를 더하더라도 (흰 칸의 수 합) - (검은 칸의 수 합)은 변하지 않으므로, 이 두 값은 반드시 같아야 한다.

만약 이 값이 같다면 항상 0으로 만들 수 있을까? 가능하다. 핵심은 같은 색깔이라면 수를 내 맘대로 이동시킬 수 있다는 점이다. 다음을 생각해 보자.

수를 (x, y)에서 두 칸 떨어진 아무 칸, 예를 들어 (x, y+2)로 t만큼 이동시키고 싶다. 그러면 (x, y+1)과 (x, y+2)에 t를 더한다. 그리고 (x, y)와 (x, y+1)에 t를 뺀다. 그러면 (x, y+1)은 그대로 유지하면서 수를 옮길 수 있다. 이 과정에서 음수가 되는 경우가 없는 것은 자명하다.

따라서 거리가 2인 같은 색 칸들끼리는 수의 이동이 자유로우므로, 이 과정을 반복하면 임의의 같은 색 칸에서는 수를 자유롭게 이동시킬 수 있다. 따라서 흰색과 검은색 칸 위에 올려져 있는 숫자들을 모두 한 곳에 몬 다음, 두 개를 같이 지우면 된다.

소스코드

http://boj.kr/0cfe0594f35e4d6a8f3036d27ee9d455

'Problem Solving > 문제풀이' 카테고리의 다른 글

[BOJ] 24973 Up Down Subsequence  (0) 2023.02.08
[BOJ] 23172 Equivalent Pipeline  (0) 2022.11.25
[BOJ] 17434 도로 청소  (0) 2022.11.25
[BOJ] 19677 Holy cow, Vim! (Hard)  (0) 2021.04.08
USACO 2020 Open contest Gold 풀이  (0) 2021.01.04