14711. 타일 뒤집기 (Easy)

 

14711번: 타일 뒤집기 (Easy)

---

처음에 검은색이었던 타일을 모두 뒤집었을 때 모든 타일이 흰색이 되는 게임판을 만들어야 한다. 

 

타일을 홀수 번 뒤집으면 색이 바뀌고, 짝수 번 뒤집으면 색이 바뀌지 않는다. 일단 첫 줄은 주어져 있으므로 나머지 줄을 완성해 보자.

 

칸의 색은 주변 4칸의 색에 의해 결정된다. 지구이의 동생이 검은색 타일만을 뒤집으므로, 주변에 검은색 타일이 홀수 개 존재한다면 이 칸의 색은 바뀐다. 반대로 검은색 타일이 짝수 개 존재한다면 이 칸의 색은 바뀌지 않는다.

 

모두 뒤집었을 때 모든 칸이 흰색이어야 하므로, 주변에 검은색 타일이 홀수 개 존재하는 칸은 처음에 검은색이어야 하며, 짝수 개 존재하는 칸은 처음에 흰색이어야 한다.

 

이때 첫 줄이 주어져 있으므로, 첫 줄을 가지고 두 번째 줄을 만들고, 두 번쨰 줄을 가지고 세 번째 줄을 만들고... 이렇게 계속 진행하면 된다. 구체적으로는 다음과 같다.

for (int i = 0; i < n - 1; i++)
{
    // i번째 줄을 가지고 (i+1)번째 줄을 만들자
    for (int j = 0; j < n; j++)
    {
        // (i, j) 주변의 검은색 칸이 홀수/짝수 개라면
        // (i+1, j) 칸은 검은색/흰색
    }
}

$(i, j)$번 칸을 본 결과를 $(i+1, j)$에 반영하는 이유는 무엇일까? $i$번 줄까지는 이미 완성됐다고 가정하기 때문에, $(i+1, j)$를 제외한 $(i, j)$의 주변 3칸은 바뀔 수 없다. 따라서 $(i+1, j)$번 칸이 $(i, j)$의 색을 결정하는 유일한 변수이다.

 

첫 번째 줄을 가지고 두 번째 줄을 결정하는 것처럼, 현재 칸을 가지고 아래 칸을 결정한다고 보면 된다. 사실 정답이 유일하다는 말은 이런 뜻이다.

---

골4치고 생각하기 어려웠다.