1018번: 체스판 다시 칠하기

 

- 관련 사이트: https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

하나씩 모두 비교하여 가장 최솟값을 구하였다.

 

1) (0, 0) 위치부터 시작 지점을 정하고 8 x 8 씩 잘라서 비교

    (예: 8 x 10인 경우, 시작 지점은 각각 (0, 0), (0, 1), (0, 2)가 된다.)

2) 시작 지점이 'B' 인 경우와 'W' 인 경우 각각 계산

3) 좌표 x, y가 짝수/홀수인지 확인하여 1)과 2) 에 대해 교체 필요한 개수 카운팅

4) 결과들을 비교하여 가장 작은 값 확인

5) 모든 계산 완료 후 가장 작은 값 출력

 

#include <iostream>
#include <vector>
using namespace std;

vector<string> matrix;

int check(int x, int y, char first, char second)
{
    int cnt = 0;
    for (int row = x; row < x + 8; row++)
    {
        for (int col = y; col < y + 8; col++)
        {
            bool row_even = (row % 2 == 0);
            bool col_even = (col % 2 == 0);
            if ((row_even && col_even || !row_even && !col_even) && matrix[row][col] != first)
                cnt++;
            else if ((row_even && !col_even || !row_even && col_even) && matrix[row][col] != second)
                cnt++;
        }
    }
    return cnt;
}

int main()
{
    int M, N;
    string str;

    cin >> M >> N;
    for (int i = 0; i < M; i++)
    {
        cin >> str;
        matrix.push_back(str);
    }
    
    int cnt;
    int result = 64;
    for (int x = 0; x <= M - 8; x++)
    {
        for (int y = 0; y <= N - 8; y++)
        {
            cnt = check(x, y, 'B', 'W');
            if (cnt < result) result = cnt;

            cnt = check(x, y, 'W', 'B');
            if (cnt < result) result = cnt;
        }
    }

    cout << result;
    return 0;
}

- 메모리: 2024 KB

- 시간: 0 ms

- 코드 길이: 1135 B

 

위의 코드에서 아래와 같이 몇가지 불필요한 로직을 제거해줄 수 있다.

 

1) (0, 0) 위치부터 시작 지점을 정하고 8 x 8 씩 잘라서 비교

    (예: 8 x 10인 경우, 시작 지점은 각각 (0, 0), (0, 1), (0, 2)가 된다.)

2) 시작 지점이 'B' 인 경우와 'W' 인 경우 각각 계산

3) 좌표 x, y의 합이 짝수/홀수인지 여부를 계산하여 1)과 2) 에 대해 교체 필요한 개수 카운팅

4) 이전 결과값, 'B'로 시작한 경우, 'W'로 시작된 경우(64 - 'B'로 시작한 경우) 중 가장 작은 값 확인 → min 함수 사용

5) 모든 계산 완료 후 가장 작은 값 출력

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> matrix;

int check(int x, int y)
{
    int cnt = 0;
    for (int row = x; row < x + 8; row++)
    {
        for (int col = y; col < y + 8; col++)
        {
            if ((row + col) % 2 == 0 && matrix[row][col] != 'B'
             || (row + col) % 2 != 0 && matrix[row][col] != 'W')
             cnt++;
        }
    }
    return cnt;
}

int main()
{
    int M, N;
    string str;

    cin >> M >> N;
    for (int i = 0; i < M; i++)
    {
        cin >> str;
        matrix.push_back(str);
    }
    
    int cnt;
    int result = 64;
    for (int x = 0; x <= M - 8; x++)
    {
        for (int y = 0; y <= N - 8; y++)
        {
            cnt = check(x, y);
            result = min({cnt, 64 - cnt, result});
        }
    }

    cout << result;
    return 0;
}

- 메모리: 2024 KB

- 시간: 0 ms

- 코드 길이: 861 B

 

추가적으로, 교체 필요한 타일 여부를 확인 시 위의 코드의 경우 아래의 로직으로 확인해주고 있다.

1) x, y 좌표의 합이 짝수이면서 타일이 'W'인 경우

2) x, y 좌표의 합이 홀수이면서 타일이 'B'인 경우

 

1)이 'B'이고 2)가 'W'로 변경하여 계산하여도 상관 없다. 'B'든 'W'든 하나의 패턴을 확인한 후 "64 - 확인된 패턴 수"를 통해 다른 하나를 구해주고 있기 때문이다.

 

위의 로직을 비트 연산자를 통해 간단히 변경이 가능하다.

1) x, y 좌표의 합이 홀수인지 확인: (row + col) % 2 != 0 → (row + col) & 1

2) 타일이 'B'가 아닌지 확인: matrix[row][col] != 'B'

3) 1과 2를 통해 조건 확인

(row + col) % 2 == 0 && matrix[row][col] != 'B' || (row + col) % 2 != 0 && matrix[row][col] != 'W'

→ (row + col) & 1 ^ matrix[row][col] != 'B'

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> matrix;

int check(int x, int y)
{
    int cnt = 0;
    for (int row = x; row < x + 8; row++)
    {
        for (int col = y; col < y + 8; col++)
        {
            cnt += ((row + col) & 1 ^ matrix[row][col] != 'B');
        }
    }
    return cnt;
}

int main()
{
    int M, N;
    string str;

    cin >> M >> N;
    for (int i = 0; i < M; i++)
    {
        cin >> str;
        matrix.push_back(str);
    }
    
    int cnt;
    int result = 64;
    for (int x = 0; x <= M - 8; x++)
    {
        for (int y = 0; y <= N - 8; y++)
        {
            cnt = check(x, y);
            result = min({cnt, 64 - cnt, result});
        }
    }

    cout << result;
    return 0;
}

- 메모리: 2024 KB

- 시간: 0 ms

- 코드 길이: 776 B