[BOJ 14711 // C++] 타일 뒤집기 (Easy)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14711번 문제인 타일 뒤집기 (Easy)이다.
문제는 아래 링크를 확인하자.

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

14711번: 타일 뒤집기 (Easy)

문제에서 주어진 첫 행은 더 건드리지 않고 시작 게임판에서의 검은 칸만을 눌렀을 때 모든 칸을 흰 칸으로 만드는 검은 칸의 배치를 찾자.

 

두 번째 행서부터 순서대로 각 행을 살필 때, 이전 행에 검은 칸이 남아있다면 그 검은 칸을 지울 수 있으면서 건드릴 수 있는 칸은 해당 검은 칸의 아래인 현재 행의 칸 뿐이다. 그러므로 그 칸은 검은 칸이 되어야한다.

 

반대로 같은 열 이전 행의 칸이 흰 색이면 바로 아래 칸을 누를 시 이전 행의 칸이 검은 칸이 되는데, 이 검은 칸을 다시 흰 칸으로 돌려놓을 방법이 없으므로 해당 칸은 흰 칸이어야 한다.

 

위의 두 경우를 보았을 때, 이전 행의 색 배치가 정해지면 다음 행의 색 배치 또한 정해지는 것을 알 수 있다.

 

답이 (유일하게) 존재하는 것은 문제에서 보장하고 있으므로, 위의 시뮬레이션을 직접 돌려 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int arr[1002][1002];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int slen; string s; cin >> slen >> s; // 흰색이 0
	cout << s << '\n';
	for (int c = 1; c <= slen; c++) {
		if (s[c - 1] == '#') {
			arr[1][c - 1] ^= 1, arr[1][c + 1] ^= 1, arr[2][c] ^= 1;
		}
	}
	for (int r = 2; r <= slen; r++) {
		for (int c = 1; c <= slen; c++) {
			if (arr[r - 1][c]) {
				cout << '#';
				arr[r][c - 1] ^= 1, arr[r][c + 1] ^= 1, arr[r + 1][c] ^= 1;
			}
			else cout << '.';
		}
		cout << '\n';
	}
}