[문제]
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
[풀이]
하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우 서로 완전 반대의 상태가 된다.
따라서 하나의 상태만 구해놓고 반대로 생각하면 된다.
검은색은 1, 흰색은 0으로 구분하여 int형이 아닌 bool형 배열을 사용했다.
먼저 맨 왼쪽 위 칸이 검은색인 경우를 구해서 b라는 배열에 저장했다.
그리고 반복문을 통해 모든 좌표에 대해서
(x,y)가 맨 왼쪽 위 칸이 되어 8*8 크기의 배열로 현재 주어진 입력에서 검은색과 흰색에 대해 각각 바꿔야하는 칸의 갯수를 확인했다.
이러한 방법으로 (0,0)부터 (N-8,M-8)까지 확인하면서 다시 칠해야 하는 정사각형의 최소 개수를 구할 수 있었다.
모든 좌표에 대해서 확인해줘야 하므로 시간초과를 걱정했지만
배열의 최대 크기가 50*50 이므로 시간초과는 발생하지 않는다.
[코드]
시간 : 0ms
#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 51
using namespace std;
struct pos{
int x,y;
};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int N,M;
bool visited[MAX][MAX]={0,};
bool map[MAX][MAX]={0,};
bool b[MAX][MAX]={0,};
void black()
{
queue <pos> q;
b[0][0]=true;
q.push({0,0});
visited[0][0]=true;
while(!q.empty()){
int x = q.front().x;
int y = q.front().y;
q.pop();
for(int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<0||ny<0||nx>=N||ny>=M||visited[nx][ny]) continue;
if(b[x][y]==false) b[nx][ny] = true;
q.push({nx,ny});
visited[nx][ny]=true;
}
}
}
int solve(int x,int y)
{
int b_cnt=0;
int w_cnt=0;
for(int i=x;i<x+8;i++){
for(int j=y;j<y+8;j++){
if(map[i][j] != b[i][j]) b_cnt++;
}
}
for(int i=x;i<x+8;i++){
for(int j=y;j<y+8;j++){
if(map[i][j] == b[i][j]) w_cnt++;
}
}
return min(b_cnt,w_cnt);
}
int main(void)
{
cin >> N >> M;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
char ch;
cin >> ch;
if(ch=='B') map[i][j]=true;
}
}
int ans = MAX*MAX;
black();
for(int i=0;i<=N-8;i++){
for(int j=0;j<=M-8;j++){
ans = min(ans,solve(i,j));
}
}
cout << ans;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 1339번. 단어 수학 (0) | 2021.01.09 |
|---|---|
| [백준] 4179번. 불! (0) | 2021.01.08 |
| [백준]20056번. 마법사 상어와 파이어볼 (2) | 2021.01.07 |
| [백준] 15653번. 구슬 탈출4 (0) | 2021.01.07 |
| [백준] 2931번. 가스관 (0) | 2021.01.05 |