컴공댕이 공부일지
[ C++/cpp ] 백준 (1018 체스판 다시 칠하기) ⭐브루트포스 알고리즘 본문
728x90
백준 1018번 체스판 다시 칠하기
( 실버 4 )
https://www.acmicpc.net/problem/1018
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
(정답 코드)
#include <iostream>
#include <vector>
using namespace std;
// 8x8 규격 내 바꿔야하는 칸 수 체크하는 함수
int check(int x, int y, const vector<vector<char>>& bw, char ch) {
int cnt_change = 0;
for(int i=0; i<8; i++) {
for(int j=0; j<8; j++) {
if(i%2 == 0 && j%2==0) { // 둘다 짝수
if(bw[x+i][y+j]==ch) continue;
}
else if (i%2 == 1 && j%2==1){ // 둘 다 홀수
if(bw[x+i][y+j]==ch) continue;
}
else { // 이외의 경우
if(bw[x+i][y+j]!=ch) continue;
}
cnt_change++; // 위에 해당하는 올바르게 배치된 경우가 아니면, 바꿔야하는 횟수 +1
}
}
return cnt_change;
}
// 주어진 nxm에서 가능한 모든 8x8을 검사하도록 하며, 바꿔야하는 칸 수가 가장 적은 것을 찾는 함수
int findMinChange(int n, int m, const vector<vector<char>>& bw) {
int cur_min = 0;
int last_min = 8*8+1;
for(int y=0; y<=m-8; y++) {
for(int x=0; x<=n-8; x++) {
// 좌표 x,y부터 8x8 칸에 바꿔야하는 최소 갯수
cur_min = min(check(x, y, bw, 'B'), check(x, y, bw, 'W'));
// last_min 갱신
if(cur_min < last_min) {
last_min = cur_min;
}
}
}
return last_min;
}
int main()
{
// 속도 향상 코드
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, m, x;
string str;
cin >> n >> m ;
vector<vector<char>> bw (n, vector<char>(m));
// 체스판 입력받기
for(int j=0; j<n; j++) {
cin >> str;
for(int i=0; i<m; i++) {
bw[j][i] = str[i];
}
}
// 최종 연산 및 출력
cout << findMinChange(n, m, bw);
return 0;
}
📖 풀이 요약
한 마디로 주어진 입력 내의 가능한 모든 8x8을 모두 검사한 것이다. (브루트포스 알고리즘)
주어진 n x m 칸을 각각 char 이차원 벡터(bw)에 넣고, 8x8 크기의 규격만큼을 모두 검사하며, B로 시작하는 경우, W로 시작하는 경우 각각에서 틀리게적혀있어 바꿔야하는 갯수를 카운트했다. 그 중 가장 적었던 카운트 값을 출력한다.
사용된 연산 함수 설명:
1. findMinChange(n, m, bw)
- 모든 8행 8열의 모든 규격을 검사하기 위해서, x,y 변수를 각 규격의 시작점으로 설정했다.
- n x m 크기의 바둑판에서 x행 y열을 기준으로 8x8 규격이 B 또는 W로 시작하는 경우의 바꿔야하는 칸 수를 check 함수로 각각 구하고, 둘 중 더 작은 값을 cur_min에 저장한다.
- 그리고 현재까지의 값보다 cur_min이 더 적다면, 최종 최솟값을 저장하는 last_min 변수를 갱신해 저장해준다.
2. check(x, y, bw, ch)
- 좌표 (x, y)에서 시작하는 8x8 영역이 B 또는 W로 시작하는 경우, 바꿔야 하는 돌의 개수를 반환한다.
- B로 시작한다면, 모든 (짝수행, 짝수열) (홀수행, 홀수열)에는 B가 있어야하고, 나머지는 W가 있어야한다.
W로 칸이 시작하는 경우도 같은 규칙이다. - B,W가 올바르게 적혀있다면 continue로 무시, 아니라면 카운트를 +1 해줬다.
복잡해보이지만.. 예제를 보면서 차근차근 규칙 찾고, 검사하는 과정을 구현하면 금방 풀리는 문제 !
728x90
'문제 풀이 > 코딩 문제 풀이 모음' 카테고리의 다른 글
[ C++/cpp ] 백준 (11561 좌표 정렬하기2) ⭐pair vector 정렬, 비교함수 (0) | 2024.07.18 |
---|---|
[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열 (0) | 2024.07.11 |
[ C++/cpp ] 백준 (2839 설탕 배달) ⭐그리디 알고리즘 (1) | 2024.03.28 |
[ C++/cpp ] 백준 (11268 절댓값 힙) ⭐자료구조, 우선순위 큐 (0) | 2024.03.28 |
[ C++/cpp ] 백준 (2840 행운의 바퀴) ⭐구현, 시뮬레이션 💥💦 (4) | 2024.03.05 |
Comments