그리드 게임 > 문제은행

본문 바로가기


알고리즘 BFS2

2503 : 그리드 게임

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 67 회    시도횟수: 768 회   



태양이는 아래와 같이 M×N 그리드 위에 놓여있는 MN개의 흰색과 검은색 돌들을 가지고 게임을 시작한다.

 

4192d3b3cf6e34dccaba2cc6f39ecec5_1451110 

 

임의의 돌 X에 대해서, X에 상, 하, 좌, 우로 인접한 4개의 돌들을 X의 이웃이라고 한다. 태양이는 위의 돌들 중에서 하나를 선택해서 돌의 색깔을 바꿀 수 있다. 그러면 이 돌의 이웃이고 같은 색을 가지는 돌들도 또한 새로운 색으로 바뀐다. 계속해서 반복적으로 색이 바뀌는 돌의 이웃들 또한 같은 색을 가지는 경우에 색이 바뀐다.

 

예를 들어, 위 그림에서 돌 A의 색을 흰색으로 바꾸면 ‘ㄷ’자 모양의 검은색 돌들이 흰색으로 바뀌어서 다음과 같이 된다.

 

4192d3b3cf6e34dccaba2cc6f39ecec5_1451110 

 

다음으로 돌 C를 흰색으로 바꾸면 다음 그림과 같이 바뀐다.

 

4192d3b3cf6e34dccaba2cc6f39ecec5_1451110 

 

그리고 돌 F를 흰색으로 바꾸고, 마지막으로 돌 E를 흰색으로 바꾸면 모든 돌들이 흰색이 된다. 따라서 모두 네 번의 색 바꾸기로 모든 돌들을 흰색으로 바꾸었다.

 

하지만 두 번만의 색 바꾸기로 모든 돌들을 같은 색으로 바꿀 수 있다. 먼저 돌 B를 검은색으로 바꾸면 다음 그림과 같이 된다.

 

4192d3b3cf6e34dccaba2cc6f39ecec5_1451110 

 

그러면 돌 A를 흰색으로 바꾸어서 모든 돌들을 흰색으로 바꾸거나, 돌 D를 검은색으로 바꾸어서 모든 돌들을 검은색으로 바꿀 수 있다. 따라서 두 번만의 색 바꾸기로 모든 돌들을 같은 색으로 바꾸었다.

 

흰색과 검은색 돌들이 M×N 그리드 위에 놓여 있을 때, 모든 돌들이 같은 색이 되도록 하는 색 바꾸기의 최소 횟수를 찾는 프로그램을 작성하시오.


첫째 줄에는 M×N 그리드를 나타내는 두 양의 정수 M과 N이 빈칸을 사이에 두고 주어진다. M과 N은 2 이상 100 이하이다.
둘째 줄부터 M개의 각 줄에는 그리드의 가로줄 한 줄에 놓여진 흰색 돌을 나타내는 0과 검은색 돌을 나타내는 1이 빈칸을 사이에 두고 연속해서 N개 주어진다.


첫째 줄에 모든 돌들이 같은 색이 되도록 하는 색 바꾸기의 최소 횟수를 출력한다.

[Copy]
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
[Copy]
2





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.