[알고리즘] 백준 1018번: 체스판 다시 칠하기 (C++), while문의 조건 and, or

이번 문제는 꽤나 건들기 싫었던 문제였다.

빡구현의 기미가 풀기 전부터 계속 느껴졌었다.

그래도 CLASS 2가 3문제 남은 시점에서 빨리 졸업하자라는 생각으로 문제에 임했다.

---

개념

 이번 문제는 브루트 포스(Brute-Force) 알고리즘을 사용했다.

브루트 포스란 완전 탐색의 의미를 가지고 '모든 경우의 수를 다 확인해보자'라는 뜻이다.

'for문을 몇 개를 쓰거나 복잡해지든 말든 일단 모든 경우를 다 탐색해보자' 같은 주관적 느낌도 생겼다.

 

그렇다고 해서 브루트 포스가 무식한(?) 느낌의 알고리즘은 아니다.

오히려 컴퓨터의 장점(단시간 안에 수억 개의 연산을 처리한다는 점)을 잘 살리는 알고리즘이다.

(책에서 그랬다..ㅎ)

 

---

고생했던 포인트

1. 8x8 사이즈의 체스판을 선언해둬야 했었다.

 처음에는 문자열로 하는 게 더 깔끔할 거 같아서 문자열로 했었는데 오류가 계속 뜨던 순간에 '문자열로 하면 입력하자마자 오버플로우가 날 수도 있다'는 말에 체스판 선언부터 싹 다 char형으로 바꿨다. (손목아 미안)

(내가 냈던 오류는 오버플로우와는 관련 없었다.)

 

2. 범위?

 

 사실상 이 부분은 한번 팍 집중하면 되는데 내가 너무... 귀찮았던 거 같다...

(범위를 설정하면 할수록 벡터 범위 오류가 계속 떠서 더 귀찮아지는 현상을 맛봤다😭)

(이래서 노트가 필요하다)

a 범위와 b 범위를 설정할 때, "뭐보다 작아야 할까... 그럼 a는?" 계속 반복이었다.

 

3. and와 or의 헷갈림

 

 이번 포스팅의 이유가 3번 때문인데 내가 작성한 코드가 주어진 예제를 다 통과하고, 게시판에 있는 반례들도 통과하는데 제출하자마자 0%만에 계속 틀렸다고 나왔었다.

그래서 다른 반례들이 있나 게시판을 뒤져보다가 나와 똑같은 반례를 발견했었다.

https://www.acmicpc.net/board/view/51269

글 읽기 - 반례좀 알려주세요... 너무 답답합니다^.ㅠ

10 10
WWBBWWWBBW
WBBWBWWWWB
WBWBWWBBWW
WBBBBBBBWW
WBBWWWBWWW
WBBBBBWWBB
WWBWWBWWBB
BWWBBWWWBB
BBWBBBBBWB
WWWBBBWWWB

답: 29
코드의 답: 30

 

 해당 코드의 피드백에서는 다른 체스판의 개수를 세는 변수의 초기화 장소가 잘못되어있다고 설명해놓으셨다.

나도 그런 걸까 싶어서 코드를 뚫어져라 봤지만 아무리 봐도 문제가 없었다.

 

그러다가 '애매한 파트의 변수들을 전부 출력해보자'라는 결론에 이르러 출력해보았다.

(이분 탐색할 때 mid값이나 low, high 등 애매한 변수들이 많을 때 많이 사용하던 방법)

 

[고치기 전의 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

char WB[8][8] = {
	'W', 'B', 'W', 'B', 'W' ,'B', 'W', 'B',
	'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
	'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
	'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
	'W', 'B', 'W', 'B', 'W', 'B' ,'W', 'B',
	'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
	'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
	'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'
};

char BW[8][8] = {
'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
'W', 'B', 'W', 'B', 'W', 'B' ,'W', 'B',
'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
'W', 'B', 'W', 'B', 'W', 'B' ,'W', 'B'
};

int minFindBlack(vector<vector<char>> board, int a, int b) {
	int cnt = 0;

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (board[i + a][j + b] != BW[i][j]) {
				cnt++;
			}
		}
	}

	return cnt;
}

int minFindWhite(vector<vector<char>> board, int a, int b) {
	int cnt = 0;

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (board[i + a][j + b] != WB[i][j]) {
				cnt++;
			}
		}
	}

	return cnt;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<char>> board(n, vector<char>(m, 'n'));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char idx;
			cin >> idx;
			if (idx == 'W' || idx == 'B') {
				board[i][j] = idx;
			}
		}
	}

	vector<int> checkArr; // 값이 얼마나 다른지 담을 배열
	int a = 0, b = 0; // board 범위 돌아다닐 때

	while (a <= n - 8 && b <= m - 8) {
		if (b > m - 8) { // 가로줄 범위 끝에 도착했을 때, 가로줄 범위를 다시 0으로 맞추고, 세로줄을 넘김
			b = 0;
			a++;
		}

		int mini = min(minFindBlack(board, a, b), minFindWhite(board, a, b));
		checkArr.push_back(mini);;
		cout << mini << ' ' << a << ' ' << b << '\n';

		b++;
	}

	sort(checkArr.begin(), checkArr.end());

	cout << checkArr[0];
	return 0;
}

 

while문 안에 있는 cout을 통해 오류를 확인할 수 있었다.

분명 9번을 탐색해서 값들을 비교하고, 최솟값이 나와야 하는데

3번밖에 출력되지 않았다는 점에서 무엇이 잘못되었는지 확 체감할 수 있었다.

 

해당 코드의 출력 (게시판에 있던 반례를 넣었을 때)

30 0 0
31 0 1
32 0 2 // 총 3번밖에 탐색하지 않았음을 알 수 있음
30

 

3번밖에 탐색하지 않았다는 건 세로줄 넘김이 없다는 것을 알 수 있게 해 주었다.

그래서 while문의 조건에 잘못이 있음을 알게 되었다.

 

고치기 전의 코드에서 while문만 따로 가져와봤다.

while (a <= n - 8 && b <= m - 8) {
		if (b > m - 8) { // 가로줄 범위 끝에 도착했을 때, 가로줄 범위를 다시 0으로 맞추고, 세로줄을 넘김
			b = 0;
			a++;
		}

		int mini = min(minFindBlack(board, a, b), minFindWhite(board, a, b));
		checkArr.push_back(mini);;
		cout << mini << ' ' << a << ' ' << b << '\n';

		b++;
	}

 

b가 m - 8을 넘었을 때는 if 조건문을 통해 다시 b를 0으로 초기화해준다고 착각했었다.

하지만, while의 조건은 a와 b가 둘 다 조건을 만족해야 돌아가기 때문에 if를 거치지 않고 바로 while문이 끝나게 된다.

 

그래서 while의 조건을 and에서 or로 바꿔주고, a의 조건을 추가하여 break가 발생하게 해 주었다.

 

while (a <= n - 8 || b <= m - 8) {
		if (b > m - 8) { // 가로줄 범위 끝에 도착했을 때, 가로줄 범위를 다시 0으로 맞추고, 세로줄을 넘김
			b = 0;
			a++;
		}

		if (a > n - 8) {
			break;
		}

		int mini = min(minFindBlack(board, a, b), minFindWhite(board, a, b));
		checkArr.push_back(mini);;
		cout << mini << ' ' << a << ' ' << b << '\n';

		b++;
	}

 

근데 사실 이러면 while문의 조건은 필요가 없다.

그래서 무한 루프(while(1))로 조건을 바꾸어도 이상이 없다.

 

---

느낀 점

무언가 잘못됐다고 느꼈을 때는 게시판도 도움이 되지만 애매한 변수들의 출력을 통해서 자신의 코드의 문제가 무엇인지 파악할 수도 있다.