시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 512 MB 1912 385 (20%) 293
문제
형석이는 M*N 그리드 위에 놓여있는 MN개의 흰색과 검은색 돌들을 가지고 게임을 한다. ![image1](/download_file/1a515cdc0e55e4c9eec0fd2c8c231a77bebac4a1bc7489113c8febb3b155c9c0/figure1.png/?show=true) 인접해 있는 같은 색의 돌들은 같은 그룹을 형성한다. 위를 보면 A~F의 6개의 그룹을 확인할 수 있다. 여기서 하나의 그룹을 뒤집게 되면, 그 그룹의 색이 반전된다. 아래의 사진은 A그룹을 뒤집었을 때의 그림이다. A라는 그룹을 뒤집었을 때, 인접한 다른 색의 그룹과 합쳐지는 것을 확인할 수 있다. (흰색 B그룹과 합쳐졌다.) ![image1](/download_file/f31b897e72dfc3cb31985432d249a69d22d17b967553ef1fe98b0b3201943c67/figure2.png/?show=true) 그 후, C를 뒤집게 되면, 아래와 같다. (마찬가지로, A,B,C,D가 한그룹이 되었다.) ![image1](/download_file/96491ad4b74c0f2ce8d4d220d5c74391270f3a57798be6faa362ff0f90c64914/figure3.png/?show=true) 그 다음 위에 있는 흰색그룹을 뒤집으면, 전체가 검은색으로 바뀐다. 이렇게 전체를 모두 같은 색으로 만드는 것이 목표이다. 문제는 위의 방법대로 진행하였을 때, 모든 바둑돌을 같은 색으로 만드는 최소한의 단계수를 구하는 것이다. 시간제한: 1초
입력
첫째 줄에는 M*N 그리드는 나타내는 두 양의 정수 M과 N이 빈칸을 사이에 두고 주어진다. M과 N은 2이상 100이하이다. 둘째 줄부터 M개의 각 줄에는 그리드의 가로줄 한 줄에 놓여진 흰색 동을 나타내는 0과 검은색 돌을 나타내는 1이 빈칸을 사이에 두고 연속해서 N개가 주어진다.
출력
첫째 줄에 모든 돌들이 같은 색이 되도록 하는 색 바꾸기의 최소 횟수를 출력한다.
힌트
### 입력 예제 ### ``` 5 6 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1 ``` ### 출력 예제 ### ``` 2 ```