[백준] 1018번 : 체스판 다시 칠하기 (C++) - 실버 3

이 문제는 백준 알고리즘에서 제공하는 단계별 문제 풀이 중 '브루트 포스' 단계에 해당한다.

링크 : https://www.acmicpc.net/problem/1018

[ 그림 1 ] 1018번 문제 전문

 

해당 문제는 입력값으로 주어진 N x M 체스판에 대하여 8 x 8 형태로 임의의 구간을 지정해 수정해야되는 체스판 칸의 개수가 최소가 되는 경우에서의 수정이 필요한 체스판 칸의 개수를 출력하는 문제이다.

 

문제 해결 시 고려 사항이다.

1. N : 행의 개수, 8 <= N <= 50
2. M : 열의 개수, 8 <= M <= 50
3. 수정이 필요한 체스칸의 개수 출력

변수 초기화에 앞서, 문제를 해결하기 위한 초기 접근 및 고려 사항에 대해 몇 가지 설명하려 한다.

 

작성자는 처음 풀었을때는 각 입력값을 벡터에 저장하고, 인덱스 별 값에 대하여 고쳐야 할 자리인지 확인하는 방식으로 코드를 작성했었는데 이런 방식은 답은 나오지만, 코드 가독성이 다소 떨어졌었다.

 

비록 문제에서는 최초 인덱스인 [0][0]의 값이 검은색인지 하얀색인지에 대해서만 고려했지만, 해당 값에 따라 각 행의 시작값과 해당 행의 각 열의 값에 대하여 조건을 작성해야 하기 때문에 추가적인 논리 연산, 혹은 중첩 조건문이 필요해져 코드가 점점 길어진다.

 

이를 해결하기 위해 다음과 같은 순서로 문제 풀이를 고쳤다.

1. 벡터에 저장하는 방식이 아닌, 최초 인덱스의 경우에 따라 다른 2가지의 경우를 string 타입의 배열로 미리 선언
2. 배열 선언의 최대 범주인 50의 길이를 가지는 string 타입의 입력값 저장용 배열을 별도 선언
3. 각 경우의 수에 대하여 고쳐야 할 체스칸의 개수를 반환하는 함수 2개 선언
4. 메인 함수에서는 주어진 N x M 체스판에서 가능한 모든 경우의 8 x 8의 크기를 가지는 부분 체스판에 대하여 고쳐야 할 체스칸의 개수를 비교하여 최소값일 경우 값을 갱신하는 형태로 작성

위의 풀이 순서에 맞게 먼저 배열을 선언한다.

string wb_board = {
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};

string bw_board = {
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"
};

string board[50];

 

이후 각 경우의 수에 대하여 고쳐야 할 체스칸의 개수를 반환하는 함수 2개를 작성한다.

// 최초 인덱스가 흰색으로 시작한다고 가정한 경우
int wb_count(int a, int b) {
    int cnt = 0;
    
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (board[a + i][b + j] != wb_board[i][j]) {
                cnt++;
            }
        }
    }
    
    return cnt;
}

// 최초 인덱스가 검은색으로 시작한다고 가정한 경우
int bw_count(int a, int b) {
    int cnt = 0;
    
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (board[a + i][b + j] != bw_board[i][j]) {
                cnt++;
            }
        }
    }
    
    return cnt;
}

 

다음으로 메인 함수이다.

int main() {
    int N, M, result = 99999;
    
    cin >> N >> M;
    
    for (int i = 0; i < N; i++) {
        cin >> board[i];
    }
    
    for (int i = 0; i + 8 <= N; i++) {
        for (int j = 0; j + 8 <= M; j++) {
            int temp = min(wb_count(i, j), bw_count(i, j));
            if (result > temp) {
                result = temp;
            }
        }
    }
    
    cout << result << '\n';
}

 

위의 코드 중 이중 for문에 대하여 기존에 작성했던 함수 wb_count와 bw_count에 대하여 B 또는 W로 시작되는 여부와 전혀 관계없이 주어진 체스판의 모든 범주에서 두 함수를 모두 실행시켜보고, 각각의 값을 비교하여 최소 수치를 정하는 과정이 조금 의아할 수 있는데, 어떠한 조건이던 모든 경우의 수를 확인해보는 과정 자체가 문제에서 요구하는 브루트 포스 방식에 부합하기 때문에 전혀 문제될 것이 없다.

 

물론 불필요하게 W로 시작하는데 bw_count로 계산하거나 B로 시작하는데 wb_count로 계산하는 과정에서 몇 가지 경우의 수는 굳이 해볼 필요 없는 계산이라고 생각될 수 있지만, 애초에 이런 경우의 수를 고려해서 최선의 방향으로만 나아가는 방식으로 문제를 해결하려 했다면 그리디 알고리즘(Greedy Algorithm)과 같은 다른 알고리즘을 채택하거나, 위의 코드에 W로 시작하면 wb_count, B로 시작하면 bw_count만 사용하도록 수정하면 된다.