(백준 1018번 체스판 다시 칠하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 5탄

🌲크리스마스에도 계속되는 알고리즘 공부! 오늘은 체스판 다시 칠하기를 해볼까 합니다~

 

완전탐색 다른 문제 풀이도 있으니 제 블로그를 참고해주세용 😚

(정답은 아닐 수 있으나.. 나름 최대한 정돈해서 풀려고 노력했슴다 히힛)

2023.12.24 - [알고리즘] - (백준 3085번 사탕게임 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 4탄

(백준 3085번 사탕게임 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 4탄

 

1018번 체스판 다시 칠하기

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

사탕 게임을 풀고 나니 이정도는 거뜬하군😚 뿌듯하다🎵

 

이 문제도 앞선 문제들과 마찬가지로 완전 탐색으로 풀면 되는 문제다!

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>

int main() {
	int N, M;
	char temp;
	scanf("%d %d ", &N, &M);
	
	// 2차원 배열의 동적할당 (전체를 new로 만들고 각 줄을 다시 동적할당)
	// char ** Arr = new char*[행의 갯수]
	// for(int i = 0; i < N; i++) Arr[i] = new char[열의 갯수]
	char** Arr = new char* [N];
	for (int i = 0; i < N; i++) Arr[i] = new char[M];
	char chess1[8][8], chess2[8][8];

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if ((i + j) % 2 == 0) {
				chess1[i][j] = 'W';
				chess2[i][j] = 'B';
			}
			else {
				chess1[i][j] = 'B';
				chess2[i][j] = 'W';
			}
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%c", &Arr[i][j]);
		}
		scanf("%c", &temp);
	}
	
	int ans = 0; int cnt1 = 0; int cnt2 = 0;
	for (int i = 0; i < N - 8 + 1; i++) {
		for (int j = 0; j < M - 8 + 1; j++) {
			/// (i, j)를 기준으로 8*8 배열을 생각한다.
			cnt1 = 0, cnt2 = 0;
			for (int a = 0; a < 8; a++) {
				for (int b = 0; b < 8; b++) {
					if (Arr[i + a][j + b] == chess1[a][b]) cnt1++;
					if (Arr[i + a][j + b] == chess2[a][b]) cnt2++;
				}
			}
			ans = std::max(ans, std::max( cnt1, cnt2));
		}
	}
	printf("%d", 64-ans);
    
	//2차원 배열의 동적할당 없애기
	for (int i = 0; i < N; i++) delete[] Arr[i];
	delete[] Arr;
	return 0;
}

 

+ 배열의 주소

(i, j) Arr[i][j]

동적할당을 했기 때문에 같은 행끼리는 연속으로 위치하고 있으나, 행이 달라지면 위치가 달라진다.

Arr[i]역시 Arr[i][0]의 위치와 다른 걸 확인할 수 있다. 

그런데 Arr[0]와 Arr의 위치는 동일하다!

char** Arr = new char* [N];
	for (int i = 0; i < N; i++) Arr[i] = new char[M];

동적할당한 코드를 보면 좀 더 명확한데, Arr[i] 각각에는 새로 동적할당되는 Arr[i][j]들(j = 0~M-1)의 주소를 저장하고 있으므로 Arr[i]와 Arr[i][j]는 위치가 다르다. Arr의 위치는 Arr[i]가 정하므로 Arr[0]와 Arr의 위치는 동일하다고 할 수 있다.