백준 온라인 저지 - 18297. Pixels

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

18297번: Pixels

오랜만에 아주 재미있는 문제를 본 것 같다.

 

N*M 격자 평면의 각 좌표마다 픽셀이 있다. 각 이미지 픽셀은 B/W(Black, White) 값을 가진다. 초기에 이 전광판의 모든 픽셀의 색깔은 W 였다. 전광판의 각 좌표마다 버튼이 한 개씩 있는데, 이를 누를 때마다 그 위치의 픽셀과 주변 픽셀(4방향), 즉 최대 5개 픽셀의 색이 토글된다.(B->W, W->B) 버튼을 잘 조작하여 입력으로 주어진 모양대로 이미지 픽셀을 만들 수 있을까?

 

N과 M의 제한이 크다. 둘의 곱이 10^5 이하가 된다고 주어져있다.

 

 

 

 

 

----- 풀이 (스포주의) -----

 

가우스 소거법을 이용한다.

 

$(i, j)$ 위치에 있는 버튼을 누르는지에 대한 정보를 $x_{i,j}$라고 하자. 변수 $NM$개와 방정식 $NM$개가 주어지는데, 이 상태로 제한시간 안에 가우스 소거법을 적용시키는건 불가능하다.

 

한 가지 중요한 고찰이 있다. 바로 한 행이나 한 열에 해당하는 $x$ 값이 주어지면 나머지 변수들의 값도 자연스럽게 하나로 결정된다는 것이다.

 

본 문제는 행렬을 전치시켜도 답이 크게 변하지 않는다. 편의상 $N \geq M$을 만족한다고 가정하자.

 

$x_{1,1}, x_{1,2}, x_{1,3}, \dots, x_{1,M}$ 만 변수로 두고, 적절한 연립방정식을 세우면 된다.

 

 

자세히 살펴보자. 입력으로 주어진 이미지 정보가 $a_{i,j}$라고 하면 (B이면 1, W이면 0)

$$ x_{2,1} = a_{1,1} + x_{1,1} + x_{1,2},\: x_{2,2} = a_{1,2} + x_{1,1} + x_{1,2} + x_{1,3}, \dots $$

주어진 숫자가 $0$ 또는 $1$이므로 $+$ 기호는 실질적으로 XOR을 의미한다. 행의 값이 커질수록 고려해야할 변수가 너무 많다. 결국 이렇게 식을 $N$번째 행까지 모두 $x_{1,.}$, $a_{.,.}$에 대한 식으로만 나타낸다면 아주 복잡해질 것이다.

 

변수를 독립적으로 생각하자. $x_{i, j}$에 대한 식에서 $x_{1, 1}$의 계수가 얼마로 나타날까? 혹은 $a_{2, 3}$의 계수가 얼마로 나타날까? 각각의 변수를 따로 생각하면 한 셀에서 연결 5 컴포넌트의 해당 변수 계수의 합이 항상 0이 될 수 밖에 없다.

 

또한, $x_{i, p}$의 식에서 $a_{1, p}$의 계수는, $x_{i-1,p}$의 식에서 $x_{1, p}$의 계수와 동일하다. 즉 $x_{1, p}$의 계수를 구하는 과정을 통해 $a_{i, p}$의 계수 값도 통째로 다 구할 수 있다.

 

이 과정을 통해 $x_{N-1,j}$, $x_{N, j}$ 방정식을 $a_{.,.}$과 $x_{1,.}$에 대한 식으로 만들 수 있다.

 

그리고 나서 $a_{N, .}$에 대한 $M$개의 식을 세우면 된다. 예를 들어, $a_{N,1} = x_{N-1,1} + x_{N,1} + x_{N,2}$ 이런식으로 말이다. 이렇게 $M$개의 변수($x_{1,1}, x_{1,2}, \dots, x_{1,M}$)에 대한 $M$개의 방정식이 나온다. 여기서 가우스 소거법을 돌린다.

 

행렬의 rank가 낮아 free variable이 생기는 경우 아무 값이나 대입해줘도 상관이 없다. 모두 $a_{.,.}$를 정당하게 색칠하는 해기 때문이다.

 

 

연립방정식을 만드는데 $O(\min(N,M) \cdot NM)$, 가우스 소거법을 돌리는데 $O(\min(N,M)^3)$으로 AC를 받기에 충분하다.

 

 

(최근 백준 온라인 저지 내 코드 카피 사고가 많이 발생하여 소스코드는 삭제합니다.)