문제 링크: https://www.acmicpc.net/problem/1018
문제 상황
- \(M×N\) 개의 단위 정사각형으로 이루어진 \(M×N\) 크기의 보드가 주어진다.
- 정사각형들은 각각 흰색과 검은색으로 칠해져 있으며 입력 데이터로 주어진다.
- 여기서 \(8×8\) 크기의 체스판을 만들기 위해 다시 칠해야 하는 단위 정사각형의 최소 갯수를 구한다.
입력
Line 1: 자연수 \(N\)과 \(M\)이 주어진다. \((8≤N,M≤50)\)
Line 2~(N+1): 보드의 각 행의 색칠 상태가 W(흰색), B(검은색)의 형태로 주어진다.
출력
다시 칠해야 하는 정사각형의 최솟값을 출력한다.
C99로 구현하였다.
1.입력과 저장
보드의 상태 정보는 행과 열로 구분할 수 있도록 입력으로 주어지므로, 행과 열 정보(인덱스)로 접근하기 용이한 2차원 배열 형태로 저장한다. 사이즈가 가변적이므로 동적 메모리 할당을 이용해 구현하자.
int N,M,i,j;
char **board;
scanf("%d %d",&N,&M); // 첫째 줄 입력 (N 과 M)
while(getchar()!='\n'); // stdin 버퍼에 남은 '\n'을 제거한다.
board=(char**)malloc(N*sizeof(char*));
board[0]=(char*)malloc(N*M*sizeof(char));
// 메모리 할당 효율성과 2차원 배열의 속성을 유지하기 위해 모든 요소를 연속된 공간에 할당한다.
for(i=0;i<N;++i){
board[i]=board[0]+i*M; // 행index×행size = board[0][0]으로부터의 i행의 상대 주소값
// 2차원 배열처럼 이용할 수 있도록 1차원 포인터가 적절한 주소를 가리키도록 설정한다.
for(j=0;j<M;++j)
board[i][j]=(getchar()=='B'); // 'B'는 1, 'W'는 0으로 저장.
while(getchar()!='\n');
}
...
free(board[0]); free(board); // 위와 같이 할당 시 할당 해제도 간단하다.
2. 완전 탐색 영역 설정
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
문제에서 이미 언급하였듯 체스판 패턴이라면 번갈아서 칠해야 하며, 따라서 두가지 경우 뿐이고 맨 왼쪽 위칸(이하 시작점)의 색으로 구분할 수 있다.
따라서 \([0,N-8]\) 구간의 행, \([0,M-8]\) 구간의 열의 모든 정사각형을 시작점으로서 검사하면 선택 가능한 모든 체스판 영역을 검사하는 것이므로, 아래와 같이 구현하면 모든 가능한 영역을 탐색할 수 있다.
int inspect(const char** board, int row, int col, char startPoint);
//board[row][col]이 startPoint일때 칠해야 할 개수를 조사하여 반환하는 함수
...
int tmp, min=64; // 다시 칠해야 하는 최악의 경우는 8×8=64개 (사실 그것보다 적지만)
for(i=0;i<=N-8;++i){
for(j=0;j<=M-8;++j){
tmp=inspect(board,i,j,0); // board[i][j]가 W일때 칠해야 할 개수
if(min>tmp) min=tmp;
tmp=inspect(board,i,j,1); // board[i][j]가 B일때 칠해야 할 개수
if(min>tmp) min=tmp; // 기존까지의 최소값과 비교하며 업데이트
}
}
printf("%d\n",min);
3. 개별 케이스 완전 탐색
이제 위에서 탐색하는 각 케이스마다 ‘칠해야 할 개수’를 조사하여 반환하는 함수 inspect만 구현하면 된다.
변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.
위와 같은 조건으로부터 2개 간격으로 같은 패턴이 반복됨을 생각해 볼 수 있다. 이는 홀짝과 연결지어 문제를 풀 수 있다는 실마리와 같다. 예를 들어,
0열 0행: 0
0열 1행: 1
0열 2행: 0
0열 3행: 1
1열 0행: 1
1열 1행: 0
1열 2행: 1
1열 3행: 0
(W는 0, B는 1로 저장하였다.)
위의 예시에서 짝수행 짝수열과 홀수행 홀수열은 0, 나머지는 1이다. 일반화를 위해 시작점의 색 (변수 startPoint)을 기준으로 생각해보면,
| 행/열 | 짝수 열 | 홀수 열 |
|---|---|---|
| 짝수 행 | startPoint |
!startPoint |
| 홀수 행 | !startPoint |
startPoint |
위 표와 같이 정리할 수 있다. 아래 XOR 연산 진리표와 비슷한 점을 발견 할 수 있다.
| ^ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
즉, XOR 연산을 이용해 i행 j열에 어떤 색이 와야하는지를 아래와 같은 식으로 알아낼 수 있다.
((i&1)^(j&1) ? !startPoint : startPoint)
이를 이용해 시작점 i행 j열의 색이 startPoint일때 몇 번을 다시 칠해야 하는지 계산하는 함수 inspect를 구현해보자. 체스판은 8×8 크기이므로 행은 \([row, row+7]\) , 열은 \([col, col+7]\) 을 탐색하면 된다.
int inspect(char** board, int row, int col, char startPoint){
int i,j,count=0;
for(i=row;i<row+8;++i){
for(j=col;j<col+8;++j){
if(board[i][j]!=((i&1)^(j&1) ? !startPoint : startPoint))
++count;
}
}
return count;
}
4. 최종 코드
앞선 단계에서 구현한 것들을 종합해보자.
#include <stdio.h>
#include <malloc.h>
int inspect(char** board, int row, int col, char startPoint){
int i,j,count=0;
for(i=row;i<row+8;++i){
for(j=col;j<col+8;++j){
if(board[i][j]!=((i&1)^(j&1) ? !startPoint : startPoint))
++count;
}
}
return count;
}
int main(void){
int N,M,i,j,tmp,min=64;
char **board;
scanf("%d %d",&N,&M);
while(getchar()!='\n');
board=(char**)malloc(N*sizeof(char*));
board[0]=(char*)malloc(N*M*sizeof(char));
for(i=0;i<N;++i){
board[i]=board[0]+i*M;
for(j=0;j<M;++j)
board[i][j]=(getchar()=='B');
while(getchar()!='\n');
}
for(i=0;i<=N-8;++i){
for(j=0;j<=M-8;++j){
tmp=inspect(board,i,j,0);
if(tmp<min) min=tmp;
tmp=inspect(board,i,j,1);
if(tmp<min) min=tmp;
}
}
printf("%d\n",min);
free(board[0]); free(board);
return 0;
}
| 결과 | 메모리 | 시간 | 코드 길이 |
|---|---|---|---|
맞았습니다!! |
1116KB | 0ms | 867B |