[백준알고리즘] 1018번: 체스판 다시 칠하기 -Python, C++

[백준알고리즘] 1018번: 체스판 다시 칠하기 -Python, C++

1018번: 체스판 다시 칠하기 (acmicpc.net)

1018번: 체스판 다시 칠하기

예전에 파이썬으로 풀었던 문제이지만 포스팅을 하지 않았었다. 예전에 풀었던 파이썬 코드는 가장 아래쪽에 넣어두었다.

 

주어진 입력이 들어오면 가장 수정을 적게해도 되는 8x8 크기의 체스판을 떼어내면 된다. 그러다 보니 직접 일일이 8x8 크기의 체스판을 떼어내는 모든 경우에 수정해야 하는 칸의 수를 카운팅 했다. 

 

처음에는 각 시작 위치마다 \(B\)로 시작하는 체스판으로 만들 때의 수정이 필요한 칸의 수와 \(W\)로 시작하는 체스판을 만들 때의 수정이 필요한 칸의 수를 각자 모두 세주었다.

그런데 이것저것 출력해보면서 문제를 풀다가 \(B\)로 시작하는 체스판으로 만들 때의 수정이 필요한 칸의 수와 \(W\)로 시작하는 체스판을 만들 때의 수정이 필요한 칸의 수의 합이 항상 64라는 것을 알게 되었다.

사실 \(B\)로 시작하는 체스판과 \(W\)로 시작하는 체스판이 정확히 반대의 경우이기 때문에 당연한 것인데 생각을 못하고 있었던 것이다.

 

이렇게 중복적으로 카운팅하는 부분이 있더라도 코드는 통과했지만, 중복되는 코드의 양이 길어지기 때문에 최종적으로는 이 부분을 줄여 아래의 코드처럼 수정했다.

 

이 문제를 풀면서 compare_board 함수를 호출하는 과정에서 const를 인자에 넣어주는 과정에서 에러가 계속 발생해서 머리가 좀 지끈거렸다 ^^;

이중 포인터인 \(board\)의 레퍼런스를 받고 싶으나, compare_board 함수 내에서는 const로 붙여주고 싶었다. 처음에는 맨 앞에만 붙여 const char**& board로 사용했지만, 이것이 왜인지 에러가 발생했다. 그러면서 찾아보니 이중 포인터의 경우 값과 각각의 포인터 위치도 변경하지 않기 위해선 const char * const * const &board처럼 \(board\), \(*board\), \(**board\)를 모두 const 처리해주어야 한다는 것을 알게 되었다. (예전에 C++ 공부하던 사이트에 있던 내용인데 다시 찾아보았다 ㅠ)

 

 

---

위에서 설명한 방법으로 작성해 통과한 C++ 코드다.

#include <iostream>
#include <climits>
#include <cstring>

void solve(void);

int main(void)
{
	solve();
}

int compare_board(const char * const * const &board, const int n, const int m)
{
	const char black_white[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 min_count = INT_MAX;

	for (int i = 0; i <= n - 8; i++)
		for (int j = 0; j <= m - 8; j++)
		{
			int count_black_start = 0;

			for (int di = 0; di < 8; di++)
				for (int dj = 0; dj < 8; dj++)
					if (board[i + di][j + dj] != black_white[di][dj])
						count_black_start++;
			
			int curr_min_count = count_black_start < (64 - count_black_start) ? count_black_start : (64 - count_black_start);
			min_count = curr_min_count < min_count ? curr_min_count : min_count;
		}

	return min_count;
}

void solve(void)
{
	int n, m;
	std::cin >> n >> m;

	char** board = new char* [n];
	for (int i = 0; i < n; i++)
		board[i] = new char[m];

	for (int i = 0; i < n; i++)
	{
		char line[50] = { 0, };
		std::cin >> line;
		memcpy(board[i], line, strlen(line));
	}

	int answer = compare_board(board, n, m);
	std::cout << answer;

	for (int i = 0; i < n; i++)
		delete[] board[i];
	delete[] board;
}

---

예전에 풀었던 파이썬 코드다. 이때의 나는 지금보다 똑똑했나보다. 두 경우의 합이 64인 것을 알고 있었다니..

chess = """WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW"""
chesses = chess.split('\n')

x, y = map(int, input().split())
pannel = []
cnt, minimum = 0, 64

for i in range(x):
    pannel.append(input())

for j in range(0, x-8+1):
    for i in range(0, y-8+1):

        for k in range(0, 8):
            for l in range(0, 8):
                if pannel[j+l][i+k] != chesses[l][k]:
                    cnt += 1
                continue
        cnt = min(cnt, 64 - cnt)
        minimum = min(minimum, cnt)
        cnt = 0
        
print(minimum)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

[참고]

혼자 연구하는 C/C++ by WinApi (soen.kr)

혼자 연구하는 C/C++ by WinApi