BOJ 10472 - 십자뒤집기

링크: https://www.acmicpc.net/problem/10472

문제

각 칸이 색칠된 상태를 0/1로 보면, 3x3 크기의 보드는 크기가 9인 상태공간을 가진다.

따라서 나타날 수 있는 보드의 상태의 수는 \(2^{9}\) = 512가지이다.

최초 보드의 상태에서 각 칸을 눌러보며 매번 9번의 상태 분기가 일어나는 BFS 탐색으로 해결 가능하다.

어떤 상태를 이미 확인했는 지에 사용되는 visit 배열은 취향에 따라 여러 형태가 가능할 것이다. 나는 000 000 000의 크기 9짜리 상태 공간을 2진법으로 변환하여 int 변수로 표현하였다. 그래서 visit[bit]로 했는데, key-value를 쓰면 string형으로 "000111000"처럼 저장할 수도 있다.

어찌되었건 중요한건 중복 확인을 할 수 있느냐이므로 편한 방법을 선택하면 되겠다.

코드