알고리즘 문제풀이 백준-1018 C++

이동복·2021년 12월 25일

알고리즘 문제풀이

목록 보기

1/19

🎲문제

주소:백준 1018

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

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

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

⌨ 입력

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

✅ 풀이

N과 M변수 생성, 체스판 생성

void init() {

    cin >> row >> col;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> table[i][j];
        }
    }
}

체스판의 크기가 8*8이기 때문에 두 번의 반복문으로 M-8, N-8을 순회할 시작점으로 잡는다.

void solve() {

    for (int i = 0; i <= row - 8; i++) {
        for (int j = 0; j <= col - 8; j++) {
            result = min(result, colorcheck(i,j));
        }
    }
}

시작점으로부터 8*8만큼의 크기만큼 전체 체스판을 순회한다. 규칙에 따라 열과 행의 인덱스를 더한 값이 짝수일때와, 홀수일 때, 두 값이 달라야한다.
짝수일 때 W, 홀수일 때 B로 기준을 잡고, 조건을 만족시켰을 때 total의 총 값을 더한다. 홀수일 때 B, 짝수일 때 W의 값은 총 타일수 64에 total값을 뺀 값과 같다. 두 값중 최소의 값을 내보낸다.

int colorcheck(int cur_r, int cur_c) {
    //col row 더한후 짝수일때, 홀수일때 체크 보드판의 절반 이상인지 확인
    int oddchk = 0, evenchk = 0;
    int total;

    for (int k = cur_r; k < cur_r + 8; k++) {
        for (int l = cur_c; l < cur_c + 8; l++) {
            
            if ((k + l )% 2 == 0 && table[k][l] == 'W')    oddchk++;
            if ((k + l) % 2 == 1 && table[k][l] == 'B')    evenchk++;
        }
    }
    total = oddchk + evenchk;

    return (total < 32 ? total : 64 - total);
}

전체 크기만큼 순회가 완료된다면, result 값을 출력한다.

전체 코드

#include <iostream>
#include <algorithm>


using namespace std;

int row, col, result = 64;
char table[52][52];

void init();
void solve();
int colorcheck(int, int);

void init() {

    cin >> row >> col;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> table[i][j];
        }
    }
}

void solve() {

    for (int i = 0; i <= row - 8; i++) {
        for (int j = 0; j <= col - 8; j++) {
            result = min(result, colorcheck(i,j));
        }
    }
}

int colorcheck(int cur_r, int cur_c) {
    //col row 더한후 짝수일때, 홀수일때 체크 보드판의 절반 이상인지 확인
    int oddchk = 0, evenchk = 0;
    int total;

    for (int k = cur_r; k < cur_r + 8; k++) {
        for (int l = cur_c; l < cur_c + 8; l++) {
            
            if ((k + l )% 2 == 0 && table[k][l] == 'W')  oddchk++;
            if((k + l) % 2 == 1 && table[k][l] == 'B')    evenchk++;
        }
    }
    total = oddchk + evenchk;

    return (total < 32 ? total : 64 - total);
}

int main(){

    init();
    solve();
    cout << result;
    return 0;
}

이동복

아는것 하나 없는 유기물 덩어리

다음 포스트

알고리즘 문제풀이 백준-1018 C++