시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 512 MB240665730.481%

문제

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

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

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

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

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

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


 

입력

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

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

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

출력

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

예제 입력 1

2
0 0
0 1

예제 출력 1

1

예제 입력 2

8
0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0

예제 출력 2

3

출처

University > 충남대학교 > 제5회 생각하는 프로그래밍 대회  D번