BOJ 10472 십자뒤집기

BOJ 10472 십자뒤집기

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

https://github.com/simjaemun2/BaekJoon/blob/25337654f7dcfeac11526bf2ab6d0190897b6c15/BOJ10472/BOJ10472.cpp

분류 : BFS, Bit operation

난이도 : H

N이 3이기 때문에 별 지장이 업지만,

N이 많이 커질 경우를 대비하여 Bit operation으로 구현하였다.

보드의 맨 윗 배열만 버튼을 누르거나 안누르는 모든 경우의 수를 따지면, 총 2 ^ N 의 경우의 수가 나온다.

그 후 0번째 행의 i번째 열이 흑색(1) 일 경우, 1번째 행의 i번째 열을 누른다.

1번 째 행을 0번째 행의 색에 따라 눌러보았을 때, 0번째 행에 검은색이 남아 있는 경우는 답을 구할 수 없는 상태로 함수를 종료한다.

이 후, 마찬가지로 1번째 행의 남은 흑색을 이용해 2번째 행을 눌러본다.

그리고 1번째 행과 2번째 행이 모두 흑색이 없을 때, 저장한 카운트를 이용하여 최소 값을 구한다.