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

풀고나니 어렵지 않았는데 풀때는 아리까리했던 문제다.

중요한건 체스판이 바뀌는 횟수를 측정하는건데, 시작점이 고정이 아니라는 것이다.

 

시작지점에 따라 체스판을 다시 색칠해야하는 횟수가 바뀐다, 우리는 이 중에서 최소를 찾아야 한다는게 문제이다.

 

그렇다면 일단 체스판 색깔을 바꾸는 로직을 짠 다음에, 시작 위치를 바꿔주는 로직을 합쳐서 코드를 짜면 되겠다는 생각으로 코딩을 시작했다.

 

우선, 나는 색깔을 바꾸는 로직을 처음에 다음과 같이 생각했다.

1. 그 줄 맨 앞의 문자를 A라는 변수에 저장한다.

2. 올바른 다음 상태(다시 칠하지 않아도 되는 경우) 저장하는 변수 B를 만든다.

3. A의 변수를 토대로 B의 값을 정한다.

ex) A가 W라면 B의 값은 B가 된다.

4. 반복문을 통해 그 줄의 값들을 비교하면서 B의 상태를 바꿔나간다. B의 상태와 배열에 들어있는 값이 다르다면 cnt++

 

이걸 반복.. 시켜서 결과를 내봤더니 내가 간과한게 있었다.

 

꼭 그줄 맨 앞의 문자에 따라서 횟수를 계산하는게 항상 최솟값을 구하는가?

 

아니었다.

 

그래서 나는 바깥에 반복문을 하나 더 만들어서

처음에는 A값을 W로 놓고, 두번째 돌때는 A값을 B로 바꿔서 돌리면서 2번 값을 측정했다.

 

이렇게 하니 진짜 최솟값이 나왔다.

 

설명을 한다고 설명을 했는데 역시 코드가 답인거같다. 코드는 다음과 같다.

 

#include <stdio.h>

int solve() {
    int M, N, start_x = 0, start_y = 0; 
    int cnt = 0, min = 99999;
    char A, B;
    char board[100][100];

    scanf("%d %d", &M, &N);

    for(int i=0;i<M;i++)
        scanf("%s", board[i]);

    while(start_y + 8 <= M){

        // printf("%d %d %c\n", start_y, start_x, A);

        //시작점이 (start_x, start_y)일때 체스판 색 교체 횟수 측정
        for(int a=0;a<=1;a++) {
            if(a == 0)
                A = 'W';
            else if(a == 1)
                A = 'B';

            for(int i=start_y;i<start_y+8;i++) {

                if(A == board[i][start_x]) {
                    if(board[i][start_x] == 'B')
                        B = 'W';
                    else if(board[i][start_x] == 'W')
                        B = 'B';
                }else if(A != board[i][start_x]) {
                    if(board[i][start_x] == 'B') {
                        B = 'B';
                        cnt++;
                    }else if(board[i][start_x] == 'W') {
                        B = 'W';
                        cnt++;
                    }
                }

                for(int j=start_x+1;j<start_x+8;j++) {
                    if(B == board[i][j]) {
                        if(board[i][j] == 'B')
                            B = 'W';
                        else if(board[i][j] == 'W')
                            B = 'B';
                    }else if(B != board[i][j]) {
                        if(board[i][j] == 'B') {
                            B = 'B';
                            cnt++;
                        }
                        else if(board[i][j] == 'W') {
                            B = 'W';
                            cnt++;
                        }
                    }
                }

                if(A == 'B')
                    A = 'W';
                else if(A == 'W')
                    A = 'B';

            }

            // printf("%c cnt : %d\n\n", A, cnt);

            if(min > cnt)
            min = cnt;

            cnt = 0;
        }

        if(start_x+8 == N) {
            start_x = 0;
            start_y++;
        }else
            start_x++;

    }

    printf("%d\n", min);
}


int main() {
    solve();
    return 0; 
}

 

굿 ㅎ 한번에 맞춰서 기분좋음