midoria   2년 전

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

문제의 내용을 이러합니다.

제가 질문드릴 것은 저 강조된 부분들 인데요.  저의 생각은 다시 칠해야 하는 정사각형 개수가 아닌 다시 칠해야 하는 칸의 개수 가 더 정확하다고 생각합니다.

예시)

8 8
WBWBBWBW
BWBWWBWB
WBWBBWBW
BWBWWBWB
WBWBBWBW
BWBWWBWB
WBWBBWBW
BWBWWBWB

채크배열로 다시 칠해야 할 경우와 그렇지 않을경우를 나타낸다면 (1 = 다시 칠해야함, 0 = 다시 안칠해도 됨)

0 0 0 0 1 1 1 1

0 0 0 0 1 1 1 1

0 0 0 0 1 1 1 1

0 0 0 0 1 1 1 1

0 0 0 0 1 1 1 1

0 0 0 0 1 1 1 1

0 0 0 0 1 1 1 1

0 0 0 0 1 1 1 1

이러한 형식으로 나타난다면 정사각형의 최소 갯수를 샐 경우에는 2가지 ( 길이가 4인 정사각형 2개 ) 가 정답입니다

하지만 100점 코드에서는 32(칸의갯수 (= 길이가 1 인 정사각형 ) 의 갯수 ) 를 구하는 형식이였습니다.

따라서 저 강조한 부분을 칸의 갯수 또는 길이가 1 인 정사각형의 갯수를 구하는게 더 명확하다고 생각합니다. (MN개의 단위 정사각형으로 이루어 졌다고 언급했지만 강조된 부분은 다시 칠해야 하는 으로 수식되어 있기에 서로 다르다고 판단할 여지가 생길 수 있음) 

제가 이 게시판에 글을 올리는게 이번이 처음이라 카테고리를 실수했을 수도 있습니다.... 그 부분을 죄송합니다.

또한 위에서 말한 부분의 검토를 부탁드립니다. ^^

그리고 위 내용은 제 선에서의 판단이기에 제 생각이 이상했을 수도 있습니다....

댓글을 작성하려면 로그인해야 합니다.