백준 1018번 : 체스판 다시 칠하기

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

2차원 배열 초기화하는 방법을 몰랐다. 1차원 배열 초기화하듯이 = { 'W' } 해도 문제 없다. like char arr [50][50]={ 'W' };

체스판이므로 행과 열을 더한 값이 짝수와 홀수로 반복된다는 것을 잊지 말자.

자료구조 과제할 때에도 항상 힘들었던 것이지만 2차원 char 배열의 비교가 제일 어렵다.

1. 아스키코드로 받은 char을 int로 저장해 비교하기 (아스키코드 참고 : https://kd3302.tistory.com/668 )
2. strcmp 이용하기

#include<iostream>
using namespace std;

int main() {
    int m,n;	//m 가로 n 세로
    cin >> n >> m;

    int arr[50][50]={ 0 };	//배열 초기화하기
    char num;

    for (int i = 0; i < n; i++) {	//입력된 배열을 arr 배열에 넣어주기
        for (int j = 0; j < m; j++) {
            cin >> num;
            arr[i][j] = num;
        }
    }

    int min = 50;	//최종 결과값인 min값 초기화

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

            int wtob = 0;
            int btow = 0;

            for (int a = i; a < i + 8; a++) {
                for (int b = j; b < j + 8; b++) {

                    if ((a + b) % 2 == 0) {
                        if (arr[a][b] == 66) 
                            btow++;
                        else
                            wtob++;
                    }
                    else {
                        if (arr[a][b] == 66)
                            wtob++;
                        else
                            btow++;
                    }
                }
            }            
            min = (min < wtob) ? min : wtob;	//한번 싹 다 돌고 나서 최솟값 검색
            min = (min < btow) ? min : btow;

        }
    }

    cout << min;	//결과 출력
    return 0;
}

이번 알고리즘은 바로 생각해내기 어려웠는데 주 포인트는 행과 열을 값을 더한 값이 계속 홀짝으로 반복된다는 것이다.

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

이렇게 7을 빼서 8X8 크기로 주어진 값을 탐색할 수 있게 해 놓는다.

int wtob = 0;
int btow = 0; 

한 블록 단위로 탐색한다고 했을 때 탐색을 시작하기 전에 wtob(b여야 하는데 w인 부분), btow(w이여야 하는데 b인 부분)을 초기화하여 블럭 단위로 수정해야 하는 최소값을 계속 남겨둘 수 있게 한다.

for (int a = i; a < i + 8; a++) {
	for (int b = j; b < j + 8; b++) { 

블럭 내에서 탐색한다.

if ((a + b) % 2 == 0) {
  	if (arr[a][b] == 66)
  		btow++;                         
  	else
  		wtob++;
} 

먼저 행과 열을 더하여 짝수가 나왔을 경우를 탐색한다. 그 부분이 66, B였다면 btow를 하나 증가시키고 아니라면 wtob를 하나 증가시킨다.

else { 
	if (arr[a][b] == 66) 
		wtob++; 
	else 
		btow++; 
} 

행과 열을 더한 값이 홀수일 경우. 결국 처음 시작이 w일 경우와 b일 경우를 나눌 필요가 없었던 것이다. w로 시작해서 기준값을 w로 설정하여 비교를 시작했을 때, 확인하는 부분들이 모두 b이라면 btow값은 계속 더해졌을 것이다. 그렇게 되면 반대의 경우 wtob는 전혀 더해지지 않았을 것이므로 결괏값인 min은 wtob와 btow 중 최솟값으로 들어가게 되는 것이다.

min = (min < wtob) ? min : wtob; 
min = (min < btow) ? min : btow; 

최종적으로 min, wtob, btow 중에서 삼중 연산항을 통해 최솟값을 찾아낸다.