23058번 - 뒤집기 게임

MBTI가 E(외향형)인 탐험가 백남이는 미지의 보물이 숨겨져 있다는 피라미드를 탐사 중이다. 무시무시한 함정들을 지나서 보물이 있는 방을 찾았지만, 보물상자를 열기 위해서는 수수께끼를 풀어야만 했다.

수수께끼의 내용은 다음과 같다.

• 양면이 검은색과 흰색으로 칠해진 돌이 있다.
• 돌은 빠짐없이 $N \times N$ 격자에 검은색 또는 흰색이 보이게 놓여 있다.
• 모든 돌을 같은 색으로 바꾸는 데 걸리는 시간을 구하여라.

그리고 백남이는 다음 중 하나의 행동을 할 수 있다. 각 행동을 하는 데 1초가 걸린다.

1. 격자의 행 또는 격자의 열을 골라 해당 줄을 전부 뒤집는다.
2. 돌 하나를 뒤집는다.

보물상자를 여는 데 걸리는 최소 시간을 구함으로써, 백남이가 무사히 보물을 얻게 도와주자!

첫 줄에 격자판의 행의 수이자 열의 수인 $N$ 이 주어진다. ($1\leq N \leq 8)$

둘째 줄부터 $N$ 개의 줄에 걸쳐 현재 각 격자의 색을 나타내는 숫자가 주어진다.

$N$ 개의 줄 중에서 $i$ 번째의 줄의 $j$ 번째 숫자는 $i$ 행 $j$ 열 격자의 색을 나타내며 '$0$'인 경우 검은색, '$1$'인 경우 흰색임을 나타낸다.

모든 돌을 같은 색으로 바꾸는 데 걸리는 최소 시간을 구하여라.