개발자 블로거의 자존심을 위해!
백준 문제 랭킹을 올리기로 마음 먹었습니다!
( 한가지만 계속하는건 싫증내는 편이라 오래 안 갈지도 모릅니다 ㅎㅎ. AB형의 단점.. )
오늘 풀이한 문제 중 재미있어 보이는 '체스판 다시 칠하기'라는 주제를 다뤄 봅니다 :)
문제 링크 : https://www.acmicpc.net/problem/1018
문제 요약
체스판은 사실 아래와 같은 모양인데요.
체스판에 딱 맞는 모양이 없어 아래와 같은 판자를 구했습니다.
8x8칸으로 잘라 쓴다고 할때 일부 타일은 불가피하게 색칠할 수 밖에 없는 상황인데요.
이 판자를 8X8 모양으로 잘라,
제일 적은 칸을 칠할 수 있는 방법을 찾는 것입니다!
만약 아래와 같이 판자를 자른다면, 절반 가까지 흰색을 칠해야 합니다.
하지만, 아래와 같이 자른다면 어떨까요?
꽤 많은 면적이 체스판과 비슷해서 12칸만 칠하면 됩니다.
판자 모양은 이것 뿐만이 아닙니다.
최소 8x8 칸에서 최대 50x50칸까지 다양한 판자 모양이 주어지는데
각 판자마다 가장 적게 칠하는 횟수를 구하는 문제이고,
역시 컴퓨터가 이 것을 소화할 수 있게 코딩하는게 목표입니다.
알고리즘 해설
FM대로 하자면 아래와 같습니다.
맨 처음에는 첫번째 8x8 의 영역에서
격자 위치를 판단해서 각각 칠할 칸수를 구하는 것입니다.
이 경우 아래그림에서 보듯이
노란색이 칠해져야 할 부분이고 32칸이나 됩니다.
이제 그 다음 8x8칸에서 마찬가지로 칠할 칸수를 셉니다.
이런 식으로 하나씩 하나씩 맨 마지막까지 센 다음에,
그 중 가장 적게 칠한 횟수를 정답으로 출력하면 됩니다.
컴퓨터는 무지 빠르기 때문에 이 정도는 초스피드이지요.
알고리즘 다른 생각
크레이는 여기서 약간 다른 생각을 했습니다.
격자모양으로 칠할 갯수를 판단하는 방법도 있겠지만,
격자칸의 색상들을 반전시켜보면 어떨까? 라구요.
그러니까 판자의 원본 모양이 아래와 같다면,
아래와 같은 모양으로 격자 위치의 색상만 반대로 바꾸는 것이지요.
이 경우 격자 위치마다 흰색, 검정새 번갈아 생각할 필요가 없습니다.
8x8칸이 모두 검정색 또는 모두 흰색으로 칠하는 것만 판단하면 되거든요.
8x8칸의 색상중 흰색과 검정색의 갯수를 세서,
흰색 또는 검정색이 가장 적은 면적을 구하면 됩니다.
아래 그림을 예로 든다면 빨간 영역 8x8칸 내에 흰색 12칸만 모두 검정으로 칠하면 됩니다.
앞의 알고리즘과 사실 원리는 동일한데요.
컴퓨터 입장에서는 색상 뒤집는 부분을 딱 한번만 수행하기 때문에
효율성면에서 완전 이득입니다.
이 설명을 이해하셨다면, 코딩을 위한 알고리즘 사고력이 생겨나시는 겁니다 :)
코딩이란 결국 알고리즘을 구체적으로 구현하는 것이니까요.
코딩
알고리즘 다른 생각 코드는 아래와 같습니다.
C++컴퓨터 언어로 작성되었으며
역시 코드는 주석이 최고이기 때문에
주저리 주저리 설명드리기 보다는 주석으로 대체합니다.
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
// 체스판 칠하기
int main()
{
// 판자의 행, 열을 입력받고
int n, m;
cin >> n >> m;
// 판자 데이터를 입력받습니다.
char map[50][51];
for (int i = 0; i < n; ++i)
{
cin >> map[i];
map[i][m] = '\0';
}
// 이 부분은 필요없는 부분이지만
// 판자 모양을 출력해보기 위해
// 심심풀이(?)로 만들어 본 것입니다.
//cout << "== MAP ==" << endl;
//for (int i = 0; i < n; ++i) cout << map[i] << endl;
//cout << endl;
// 역발상 : 격자 위치의 흰색, 검정색상을 반전시킵니다
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if ((i + j) % 2 == 0) {
if (map[i][j] == 'W')map[i][j] = 'B';
else map[i][j] = 'W';
}
// 역시 판자 모양을 출력하는 부분
//cout << "== MAP ==" << endl;
//for (int i = 0; i < n; ++i) cout << map[i] << endl;
//cout << endl;
// 최저 횟수는
// 우선 최대치로 잡아놓습니다.
int paint_low = n * m;
// 8x8칸을 세기위한
// 시작 위치에 대해
// 반복을 돌립니다.
for(int i = 0; i <= n - 8; ++i)
for (int j = 0; j <= m - 8; ++j){
// 흰색, 검정색 갯수를 세기 위해
// 0개로 세팅해 놓고
int check_w = 0;
int check_b = 0;
// 8x8칸에 대한
// 반복을 돌립니다.
for(int ii=0;ii<8;++ii)
for (int jj = 0; jj < 8; ++jj){
// 그러면서 흰색과 검정색의
// 갯수를 셉니다.
if (map[i + ii][j+jj] == 'W')check_w++;
else check_b++;
}
// 그동안 조사한 최저갯수보다
// 흰색 타일 갯수가 적으면 최저갯수를 변경합니다.
if (check_w < paint_low)paint_low = check_w;
// 그동안 조사한 최저갯수보다
// 검정 타일 갯수가 적으면 최저갯수를 변경합니다.
if (check_b < paint_low)paint_low = check_b;
}
// 제일 적은 갯수를 출력합니다.
cout << paint_low;
return 0;
}이 문제를 백준 알고리즘에 돌려보면,
아래와 같이 멋지게 통과!
필요하신 분에게 도움이 되셨울자 모르겠군요 :)
도움이 되셨다면 공감 한방, 댓글은 굿잡!
감사합니다~
