아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

뒤집기 게임

면접 대비

시간 제한1초메모리 제한512 MB

요약
0과 1로 채워진 N x N 격자에서 행 전체나 열 전체를 뒤집거나 한 칸만 뒤집는 연산만으로 모든 칸을 같은 색으로 만드는 최소 횟수를 구한다.
난이도

보통10점 중 5점

유형
완전 탐색, 비트 연산, 구현, 배열
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

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

입력

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

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

NN 개의 줄 중에서 ii 번째의 줄의 jj 번째 숫자는 ii 행 jj 열 격자의 색을 나타내며 '00'인 경우 검은색, '11'인 경우 흰색임을 나타낸다.

출력

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

예제2

  1. 예제 1

    입력
    2
0 0
0 1
    예상 출력
    1

  2. 예제 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
    예상 출력
    3