백준-체스판 다시 칠하기(1018번)

문제

n,m값을 입력받습니다.

 

row: n, col: m 을 가지는 체스판이라고 가정합니다.

 

각 칸마다 W또는 B를 입력받습니다. 

 

가장 좌측위가 W인 체스판, 또는 B인 체스판으로 구성하고자 하는데, 이떄의 크기는 8x8로 만들어주려고 합니다. 

임의의 위치에서 잘라서 8x8체스판을 만들려고 하는데 그 중에서 정상적인 체스판으로 만들기 위해서,

다시 칠해야 하는 최소의 칸 수를 구하는 문제 입니다.

---

풀이

 

저 같은 경우는 먼저 n,m을 입력받은 후, 동적할당을 통해 2차원 배열을 만들어 주었습니다.

 

(참고로 int** arr 은 전역변수로 만들었습니다. 함수 속에서 사용하기 위해서+ 함수 매개변수를 줄이려고)

    int n,m;
    cin>>n>>m;
    
    arr=new int*[n];
    for(int i=0; i<n; i++)
    {
        arr[i]=new int[m];
    }

이제 가상의 체스판을 arr[row][col]형태로 접근이 가능해집니다.

 

 

 

 

그런후, 각 체스판의 색을 입력받습니다.

for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            char c;
            cin>>c;
            if(c=='B')
                arr[i][j]=0;
            else
                arr[i][j]=1;
        }
    }

저 같은 경우에는

B(검정)인 경우에는 0을 저장,

W(흰색)인 경우에는 1을 저장해줬습니다.

 

 

 

 

이제 체스판을 검사해주는 함수를 만들어주겠습니다.

int count(int row, int col) //인자로 가장 왼쪽위의 row,col값을 받아서 검사
{
    int Bsave=0; //시작이 검정일때, 다시 칠해야 하는 정사각형의 수
    int Wsave=0; //시작이 흰색일때, 다시 칠해야 하는 정사각형의 수
    
    for(int i=row; i<row+8; i++)
    {
        for(int j=col; j<col+8; j++)
        {
            if((i+j)%2==(row+col)%2) 
            {
                if(arr[i][j]!=0) //시작 검정기준 카운트
                    Bsave++;
                else if(arr[i][j]!=1) //시작 흰색기준 카운트
                    Wsave++;
            }
            else
            {
                if(arr[i][j]!=1) //시작 검정기준 카운트
                    Bsave++;
                if (arr[i][j] != 0) //시작 흰색기준 카운트
                    Wsave++;
            }
        }
    }
    
    return (Bsave>Wsave ? Wsave : Bsave);
}

매개변수로 받는 row,col값은 가장 좌측위의 위치를 입력받습니다. (행렬의 그것과 동일하게)

 

Bsave는 좌측위가 검정인 체스판일 경우의 최소 색칠해야하는 칸 수를 의미하고, 

Wsave는 좌측위가 흰색인 체스판일 경우의 최소 색칠해야하는 칸 수를 의미합니다.

 

그리고 2중 for문을 통해서 모든 8x8칸을 검사해줍니다. 

 

이때 if문에서 (i+j)%2 == (row+col)%2 를 해줬는데, 왜 사용하였냐면

체스판의 규칙대로라면, (행+열)%2 한 값이 같은 칸은 전부 같은 색이여야 하기 때문입니다. 

아래의 예시로 확인해보겠습니다.

빨간색 동그라미 칸을 예시로 들면 

 

첫번째 동그라미는 (0+0)%2 ==0 이고, 두번째 동그라미는(2+2)%2==0 으로 동일합니다. 

 

그리고 마지막으로 Bsave와 Wsave중에 더 작은값을 return해줌으로서 함수가 끝납니다.

 

 

 

 

 

이제 위에서 만든 함수를 활용해야합니다.

    int min_paint=64;

    for(int i=0; i<=n-8; i++)
    {
        for(int j=0; j<=m-8; j++)
        {
            int temp=count(i,j);
            if(min_paint>temp)
            {
                min_paint=temp;
            }
        }
    }
    cout<<min_paint;

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

min_paint변수는 모든 칸을 검사했을때 최소의 다시 칠해야하는 칸수를 저장하기 위한 변수입니다.

초기값은 8x8체스판에서 색칠해야 하는 수는 64보다 무조건 작기 때문에 64로 해놨습니다. 

 

그렇게 2중 for문을통해서 가능한 좌측위의 row,col값을 구해서 위에서 구현했던 count함수에 넣어줍니다. 

 

그리고 최종으로 나온 결과인 min_paint를 출력해준 후, 

 

동적할당 해제를 해주면 끝나게됩니다.

 

 

 

 

 

#include<iostream>
using namespace std;

int** arr;

int count(int row, int col) //인자로 가장 왼쪽위의 row,col값을 받아서 검사
{
    int Bsave=0; //시작이 검정일때, 다시 칠해야 하는 정사각형의 수
    int Wsave=0; //시작이 흰색일때, 다시 칠해야 하는 정사각형의 수
    
    for(int i=row; i<row+8; i++)
    {
        for(int j=col; j<col+8; j++)
        {
            if((i+j)%2==(row+col)%2) 
            {
                if(arr[i][j]!=0) //시작 검정기준 카운트
                    Bsave++;
                else if(arr[i][j]!=1) //시작 흰색기준 카운트
                    Wsave++;
            }
            else
            {
                if(arr[i][j]!=1) //시작 검정기준 카운트
                    Bsave++;
                if (arr[i][j] != 0) //시작 흰색기준 카운트
                    Wsave++;
            }
        }
    }
    
    return (Bsave>Wsave ? Wsave : Bsave);
}


// 0:검정, 1:흰색
int main()
{
    int n,m;
    cin>>n>>m;
    
    arr=new int*[n];
    for(int i=0; i<n; i++)
    {
        arr[i]=new int[m];
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            char c;
            cin>>c;
            if(c=='B')
                arr[i][j]=0;
            else
                arr[i][j]=1;
        }
    }


    int min_paint=64;

    for(int i=0; i<=n-8; i++)
    {
        for(int j=0; j<=m-8; j++)
        {
            int temp=count(i,j);
            if(min_paint>temp)
            {
                min_paint=temp;
            }
        }
    }
    cout<<min_paint;

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

최종 코드입니다.