[C/C++] BOJ 1018번 : 체스판 다시 칠하기

Jnary·2022년 7월 24일
0

BOJ

목록 보기
6/9
post-thumbnail

1. 문제

https://www.acmicpc.net/problem/9177

2. 풀이

1시간동안이나 붙잡고 있었던 문제. 풀면서 계속 이게 왜 실버4? 하는 생각이...
다른 분들 코드 엄청 깔끔하던데 아무도 저와 같은 알고리즘은 생각하지 않으셨던 것 같아 올립니당..ㅎ (자랑X)

우선 입력받는 것을 draw 라는 이차원 배열에 넣었습니다.
그리고 8*8을 찾을 때 왼쪽 맨 위를 기준점으로 잡아 check 함수를 호출시킵니다.
왼쪽 맨 위가 기준점이기 때문에, 왼쪽 맨 위 인덱스를 (i,j)라고 했을 때 i <= N-8, j <= M-8 이어야 합니다.
그 이상이 된다면 8칸을 확보할 수 없을 테니까요!

한 기준점을 잡아 check함수를 호출시키고 난다면, tmp_draw라는 배열에 값을 모두 옮겨주게 됩니다.
tmp_draw 배열을 왜 사용하게 됐느냐? 하면,
WBBB일 경우, WBWB로 다시 칠하고 나서 계속 검사를 진행해야하기 때문에 원본 배열의 값이 변경됩니다.
하지만 다른 기준점으로 인해 check가 호출되고 나면, 이전의 배열 값으로 검사를 해야하기 때문에
tmp_draw는 원본 배열을 건들이지 않기 위해 쓰였습니다.

그 이후, 반복문을 돌면서 현재의 인덱스에 있는 값이 이전의 인덱스에 있는 값과 같은지 비교하고,
같으면 cnt1값을 늘리고 다르면 넘어갑니다.
BAA 로 시작되는 데이터일 경우, B로 시작했을 경우에 다시 칠하는 횟수가 cnt1에 저장되고
B->A로 바꾸어 A로 시작했을 경우에 다시 칠하는 횟수가 cnt2에 저장됩니다.

cnt1, cnt2 둘 중 작은 값이 cnt에 저장이 되고 res는 전역변수로서 이렇게 할당받은 cnt들의 값을 비교하여 가장 작은 값을 저장하게 됩니다. 아래 코드를 통해 살펴봅시다!

3. 답

#include <iostream>
#include <algorithm>

using namespace std;

char draw[50][50];
int N, M;
int res;

void check(const int i, const int j) {
    char tmp_draw[8][8];

    int k = 0;
    for (int a = i; a < i + 8; a++, k++) {
        int l = 0;
        for (int b = j; b < j + 8; b++, l++) {
            tmp_draw[k][l] = draw[a][b];
        }
    }

    int cnt1 = 0;
    for (int a = 0; a < 8; a++) {
        for (int b = 1; b < 8; b++) {
            if (tmp_draw[a][b-1] == tmp_draw[a][b]) {
                cnt1++;
                if (tmp_draw[a][b-1] == 'W')
                    tmp_draw[a][b] = 'B';
                else
                    tmp_draw[a][b] = 'W';
            }
        }

        if(a+1 < 8 && tmp_draw[a][7] != tmp_draw[a+1][0]) {
            cnt1++;
            if (tmp_draw[a+1][0] == 'W')
                tmp_draw[a+1][0] = 'B';
            else
                tmp_draw[a+1][0] = 'W';            
        }
    }
/***********************************************************/
	//첫 시작을 바꿔서 검사
    k = 0;
    for (int a = i; a < i + 8; a++, k++) {
        int l = 0;
        for (int b = j; b < j + 8; b++, l++) {
            tmp_draw[k][l] = draw[a][b];
        }
    }

    int cnt2 = 1;
    if (tmp_draw[0][0] == 'W')
        tmp_draw[0][0] = 'B';
    else
        tmp_draw[0][0] = 'W';

    for (int a = 0; a < 8; a++) {
        for (int b = 1; b < 8; b++) {
            if (tmp_draw[a][b-1] == tmp_draw[a][b]) {
                cnt2++;
                if (tmp_draw[a][b-1] == 'W')
                    tmp_draw[a][b] = 'B';
                else
                    tmp_draw[a][b] = 'W';
            }
        }
        if(a+1 < 8 && tmp_draw[a][7] != tmp_draw[a+1][0]) {
            cnt2++;
            if (tmp_draw[a+1][0] == 'W')
                tmp_draw[a+1][0] = 'B';
            else
                tmp_draw[a+1][0] = 'W';            
        }
    }

    int cnt = min(cnt1, cnt2);	//첫 시작을 바꾸지 않은 것과 바꾼 것, 둘 중 작은 값 대입
    res = min(res, cnt);
}

int main() {
    cin >> N >> M;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> draw[i][j];
    
    res = 999;
    for (int i = 0; i <= N-8; i++) {
        for (int j = 0; j <= M-8; j++) {
            check(i, j);
        }
    }

    cout << res << endl;
}

어디 내놓기 부끄러운 코드지만... 1시간 걸쳐 풀었다는 거에 의의를 두겠슴니다 ^^
( 이상 컴린이
)

profile
숭실대학교 컴퓨터학부 21

0개의 댓글