[백준] 1018번 : 체스판 다시 칠하기 (C++) - 실버 3
이 문제는 백준 알고리즘에서 제공하는 단계별 문제 풀이 중 '브루트 포스' 단계에 해당한다.
링크 : https://www.acmicpc.net/problem/1018
해당 문제는 입력값으로 주어진 N x M 체스판에 대하여 8 x 8 형태로 임의의 구간을 지정해 수정해야되는 체스판 칸의 개수가 최소가 되는 경우에서의 수정이 필요한 체스판 칸의 개수를 출력하는 문제이다.
문제 해결 시 고려 사항이다.
- N : 행의 개수, 8 <= N <= 50
- M : 열의 개수, 8 <= M <= 50
- 수정이 필요한 체스칸의 개수 출력
변수 초기화에 앞서, 문제를 해결하기 위한 초기 접근 및 고려 사항에 대해 몇 가지 설명하려 한다.
작성자는 처음 풀었을때는 각 입력값을 벡터에 저장하고, 인덱스 별 값에 대하여 고쳐야 할 자리인지 확인하는 방식으로 코드를 작성했었는데 이런 방식은 답은 나오지만, 코드 가독성이 다소 떨어졌었다.
비록 문제에서는 최초 인덱스인 [0][0]의 값이 검은색인지 하얀색인지에 대해서만 고려했지만, 해당 값에 따라 각 행의 시작값과 해당 행의 각 열의 값에 대하여 조건을 작성해야 하기 때문에 추가적인 논리 연산, 혹은 중첩 조건문이 필요해져 코드가 점점 길어진다.
이를 해결하기 위해 다음과 같은 순서로 문제 풀이를 고쳤다.
- 벡터에 저장하는 방식이 아닌, 최초 인덱스의 경우에 따라 다른 2가지의 경우를 string 타입의 배열로 미리 선언
- 배열 선언의 최대 범주인 50의 길이를 가지는 string 타입의 입력값 저장용 배열을 별도 선언
- 각 경우의 수에 대하여 고쳐야 할 체스칸의 개수를 반환하는 함수 2개 선언
- 메인 함수에서는 주어진 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만 사용하도록 수정하면 된다.