국기 인식
면접 대비시간 제한1초메모리 제한128 MB
6x9 문자 행렬이 주어질 때, 가로 2행씩 또는 세로 3열씩 세 구간으로 나누고 중간 구간 색이 양쪽과 달라야 하는 단순 깃발로 바꾸는 데 필요한 최소 변경 횟수를 구합니다.
문제
희원이는 국기를 인식하는 시스템을 만들었다. 이 시스템은 국기를 6*9 크기의 행렬로 필터링한 뒤 인식한다. 행렬의 각 칸에는 색을 나타내는 알파벳 대문자가 들어 있다.
아직 개발 초기 단계라서, 이 시스템은 다음과 같이 세 부분으로 나뉜 간단한 형태의 국기만 인식할 수 있다.
CCCCCCCCC CCCCCCCCC ZZZBBBCCC ZZZAAAZZZ
CCCCCCCCC CCCCCCCCC ZZZBBBCCC ZZZAAAZZZ
BBBBBBBBB BBBBBBBBB ZZZBBBCCC ZZZAAAZZZ
BBBBBBBBB BBBBBBBBB ZZZBBBCCC ZZZAAAZZZ
PPPPPPPPP CCCCCCCCC ZZZBBBCCC ZZZAAAZZZ
PPPPPPPPP CCCCCCCCC ZZZBBBCCC ZZZAAAZZZ
간단한 형태란 6*9 행렬을 가로로 세 부분(각각 2행)으로 나누거나, 세로로 세 부분(각각 3열)으로 나눈 뒤, 각 부분의 모든 칸이 같은 색인 경우를 말한다. 가운데 부분의 색은 양쪽 두 부분의 색과 달라야 한다. 양쪽 두 부분의 색은 서로 같아도 되고 달라도 된다.
인식된 국기가 주어졌을 때, 간단한 형태가 되도록 바꿔야 하는 문자의 최소 개수를 구하는 프로그램을 작성하시오.
입력
총 6개의 줄에 걸쳐, 각 줄마다 9개의 알파벳 대문자가 주어진다.
출력
간단한 형태가 되기 위해 바꿔야 하는 문자의 최소 개수를 첫째 줄에 출력한다.