백준/1018/brute force/체스판 다시 칠하기
이번 풀이는 썩 만족스러운 풀이는 아니었다 나중에 STL개념이 정립되면 다시한번 정리하려고한다.
우선 체스판을 고치는 오류는 2가지로 생각했다.
- 위 아래에 서로 색이 다를경우
- 양 옆에 색이 다를 경우
for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (i == 0 && j == 0) continue; else if (j == 0) { if (arr[i - 1][j] == arr[i][j]){ if (arr[i][j] == 'B') arr[i][j] = 'W'; else arr[i][j] = 'B'; count++; } } else { if (arr[i][j - 1] == arr[i][j]) { if (arr[i][j] == 'B') arr[i][j] = 'W'; else arr[i][j] = 'B'; count++; } } } }
오류가 발생했을때 색을 다시 칠하고 카운터를 증가시키는 로직을 만들었습니다.
위 아래가 다를 경우는 체스판에 첫번째 행 첫번째 열를 제외하고 첫번째 열 일경우 바로 위에 요소와 비교 하여 색이 다를 경우 다시 칠하고 카운터를 up하였고
양 옆에 경우는 바로 전 원소와 비교하여 색이 다를경우 카운터를 up하였습니다.
색을 다시칠하는 이유는 해당 원소를 고치지 않고 넘어가면 다음 원소에서 또 같은 원소가 나왔을 경우 역시 카운트하기 때문입니다.
하지만 문제에서 간과한게 있었으니 저 보드에서 8*8에 정사각형 모양을 만들고 거기에 체스판이 되도록 색칠을 하는 것이었습니다.
그래서 이번에는 체스판을 만들 수 있는 경우의 수를 모두 탐색하기로 했고 그렇게 하려면 현재 주어진 보드판 즉, N*M에 보드판에서 최대 N-8,M-8까지의 범위를 차례대로 탐색하면 됩니다.
for (int i = 0; i <= N - 8; i++) { for (int j = 0; j <= M - 8; j++) { for (int a = 0; a < N; a++) { for (int b = 0; b < M; b++) { temp[a][b] = arr[a][b]; } } if (temp[i][j] == 'B'&&f == 1) { temp[i][j] = 'W'; count++; } else if (temp[i][j] == 'W'&&f == 1) { temp[i][j] = 'B'; count++; } for (int k = i; k < (i + 8); k++) { for (int l = j; l < (j + 8); l++) { if (i == k && j == l) continue; else if (j == l) { if (temp[k - 1][l] == temp[k][l]) { if (temp[k][l] == 'B') temp[k][l] = 'W'; else temp[k][l] = 'B'; count++; } } else { if (temp[k][l - 1] == temp[k][l]) { if (temp[k][l] == 'B') temp[k][l] = 'W'; else temp[k][l] = 'B'; count++; } } } } if (min > count) { min = count; } count = 0; } } if (min == 2500) min = 0;
그렇게 되도록 위에 로직을 바꾸었고 더불어 원본이 파괴되지 않도록 temp 배열을 새로 선언하였습니다. 예제를 넣어가면 실행 하던 도중
9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW
이 예제에 답이 31인데 제가 만든 프로그램은 32라는 답을 출력했습니다. 이유를 생각해보면서 문제를 다시 읽던 중 맨 왼쪽 첫번째 원소가 '검은색 또는 하얀색일 경우'에 라는 지문이 눈에 들어왔고 위에 예시를 잘 생각해보니 첫번째 원소가 W로 나와야만 맨 아래에 W가 바뀌지 않고 31이라는 답을 출력할 수 있음을 깨닫고 이번에는 원래 상태로 한번 배열을 검사하고 두번째는 첫번째 원소를 원래 원소의 반대로 바꾸고 검사하도록 하였습니다.
for (int i = 0; i <= N - 8; i++) { for (int j = 0; j <= M - 8; j++) { for (int f = 0; f < 2; f++) { for (int a = 0; a < N; a++) { for (int b = 0; b < M; b++) { temp[a][b] = arr[a][b]; } } if (temp[i][j] == 'B'&&f == 1) { temp[i][j] = 'W'; count++; } else if (temp[i][j] == 'W'&&f == 1) { temp[i][j] = 'B'; count++; } for (int k = i; k < (i + 8); k++) { for (int l = j; l < (j + 8); l++) { if (i == k && j == l) continue; else if (j == l) { if (temp[k - 1][l] == temp[k][l]) { if (temp[k][l] == 'B') temp[k][l] = 'W'; else temp[k][l] = 'B'; count++; } } else { if (temp[k][l - 1] == temp[k][l]) { if (temp[k][l] == 'B') temp[k][l] = 'W'; else temp[k][l] = 'B'; count++; } } } } if (min > count) { min = count; } count = 0; } } } if (min == 2500) min = 0;
이 문제를 통해 얻은 교훈은 옛날 초,중,고 시절 들었던 문제를 정확히 읽자 였습니다..
풀이
첫번째 풀이
#include<iostream>
using namespace std;
int main(void) {
int N, M;
cin >> N >> M;
int count = 0;
char arr[50][50];
for(int i=0;i<N;i++)
for (int j = 0; j < M; j++) {
cin >> arr[i][j];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i == 0 && j == 0)
continue;
else if (j == 0) {
if (arr[i - 1][j] == arr[i][j]){
if (arr[i][j] == 'B')
arr[i][j] = 'W';
else
arr[i][j] = 'B';
count++;
}
}
else {
if (arr[i][j - 1] == arr[i][j]) {
if (arr[i][j] == 'B')
arr[i][j] = 'W';
else
arr[i][j] = 'B';
count++;
}
}
}
}
cout << count << endl;
}두번째 풀이
#include<iostream>
using namespace std;
int main(void) {
int N, M;
cin >> N >> M;
int count = 0;
int min = 2500;
char arr[50][50];
char temp[50][50];
for(int i=0;i<N;i++)
for (int j = 0; j < M; j++) {
cin >> arr[i][j];
}
for (int i = 0; i <= N - 8; i++) {
for (int j = 0; j <= M - 8; j++) {
for (int a = 0; a < N; a++) {
for (int b = 0; b < M; b++) {
temp[a][b] = arr[a][b];
}
}
if (temp[i][j] == 'B'&&f == 1) {
temp[i][j] = 'W';
count++;
}
else if (temp[i][j] == 'W'&&f == 1) {
temp[i][j] = 'B';
count++;
}
for (int k = i; k < (i + 8); k++) {
for (int l = j; l < (j + 8); l++) {
if (i == k && j == l)
continue;
else if (j == l) {
if (temp[k - 1][l] == temp[k][l]) {
if (temp[k][l] == 'B')
temp[k][l] = 'W';
else
temp[k][l] = 'B';
count++;
}
}
else {
if (temp[k][l - 1] == temp[k][l]) {
if (temp[k][l] == 'B')
temp[k][l] = 'W';
else
temp[k][l] = 'B';
count++;
}
}
}
}
if (min > count) {
min = count;
}
count = 0;
}
}
if (min == 2500)
min = 0;
cout << min << endl;
}세번째 풀이
#include<iostream>
using namespace std;
int main(void) {
int N, M;
cin >> N >> M;
int count = 0;
int min = 2500;
char arr[50][50];
char temp[50][50];
for(int i=0;i<N;i++)
for (int j = 0; j < M; j++) {
cin >> arr[i][j];
}
for (int i = 0; i <= N - 8; i++) {
for (int j = 0; j <= M - 8; j++) {
for (int f = 0; f < 2; f++) {
for (int a = 0; a < N; a++) {
for (int b = 0; b < M; b++) {
temp[a][b] = arr[a][b];
}
}
if (temp[i][j] == 'B'&&f == 1) {
temp[i][j] = 'W';
count++;
}
else if (temp[i][j] == 'W'&&f == 1) {
temp[i][j] = 'B';
count++;
}
for (int k = i; k < (i + 8); k++) {
for (int l = j; l < (j + 8); l++) {
if (i == k && j == l)
continue;
else if (j == l) {
if (temp[k - 1][l] == temp[k][l]) {
if (temp[k][l] == 'B')
temp[k][l] = 'W';
else
temp[k][l] = 'B';
count++;
}
}
else {
if (temp[k][l - 1] == temp[k][l]) {
if (temp[k][l] == 'B')
temp[k][l] = 'W';
else
temp[k][l] = 'B';
count++;
}
}
}
}
if (min > count) {
min = count;
}
count = 0;
}
}
}
if (min == 2500)
min = 0;
cout << min << endl;
}