2002년 가을학기 문제해결기법 - 문제 11

색깔바꾸기

다음 그림과 같이 3*3 정사각형 모양이 있다. 각 칸은 검은색이나 흰색이다. 칸을 하나 누르면 그 칸과 가로, 세로, 대각선으로 이웃한 칸들의 색이 반대로 변한다. 예를 들어, 1번을 누르면 1, 2, 4, 5 번의 색이 반대로 변한다. 6번을 누르면 2, 3, 5, 6, 8, 9번의 색이 반대로 변한다. 물론 5번을 누르면 1, 2, 3, 4, 5, 6, 7, 8, 9번의 색이 반대로 변한다.

1	2	3
4	5	6
7	8	9

예를 들어 아래 그림 (a)에서 6번 칸을 누르면 그림 (b)로 변하고, 여기서 1번 칸을 누르면 그림 (c)가 되어 모두 하얗게 변한다. (a) 그림을 모두 하얗게 만드는데 누르는 회수는 2이다.

■□■       ■■□       □□□

■□■       ■■□       □□□

□■■       □□□       □□□

(a)          (b)           (c)

각 칸이 검은 색이나 흰색으로 칠해진 3*3 정사각형이 주어질 때, 이를 모두 흰색이 되도록 하는데, 누르는 회수를 최소로 하는 방법을 찾는 프로그램을 작성하시오.

프로그램 이름과 설명 파일 이름은 각각 color.xxx, color.yyy라고 하고 실행 파일 이름은 color.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫 줄에  b와 w로 이루어진 길이 9인 문자열이 주어진다. 이 글자들 사이에는 빈칸이 없다. 이들은 차례로 1, 2, ..., 9에 해당하는 칸의 색을 나타내는데, b는 검은색이고, w는 흰색이다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 모든 칸이 흰색이 되도록 하는데 필요한 누르는 최소 회수를 출력한다. 모두 흰색으로 바꾸는 것이 불가능하면 -1을 출력한다.

입력과 출력의 예 (1)

INPUT.TXT

wbbwbbwww

OUTPUT.TXT

1

입력과 출력의 예 (2)

INPUT.TXT

wwwwwwwww

OUTPUT.TXT

0