[ SWEA 6731 ] 홍익이의 오델로 게임 (C++)

SWExpertAcademy의 홍익이의 오델로게임(6731 / D4) 문제이다.

[ 문제풀이 ]

문제를 해결한 후에도 의문이 조금 남을만큼 몇 번의 테스트를 통해서 규칙을 찾은 다음에 그 규칙에 맞게 해결한 문제였다..

그러면 지금부터 몇 번의 테스트를 통해서 무슨 규칙이 있는지 한번 알아보자.

가장 처음에 위와 같은 형태가 있다. 위의 상태에서 빨간색 점으로 칠해진 원을 한번 뒤집어 보자.

그럼 다음과 같은 형태로 맵이 바뀌게 될 것이다.

여기서 무슨 규칙을 알아낼 수 있을까 ?? 사실상 규칙은 물론이고, 너무나도 당연한 결과이기 때문에 위의 맵을 보면서

별다른 생각을 하기는 쉽지 않다. 그런데 혹시나 하는 마음에서 검은색돌의 갯수를 한번 카운트 해보자.

검은색돌의 갯수는 "현재 좌표를 기준으로 해당 좌표의 행과 열에 총 몇개의 검은색 돌이 있는지" 카운트 해보자.

카운트를 해서 적어보면 다음과 같을 것이다.

가장 왼쪽 위의 좌표인 (0, 0)을 보게되면, 0행에 검은돌이 1개, 0열에 검은돌이 1개가 있어서, 총 2개가 있게 된다.

(0, 0)의 오른쪽 좌표인 (0, 1)의 좌표를 보게되면, 0행에 검은돌이 0개, 1열에 검은돌이 4개가 있어서 4개가 된다.

이런식으로 한 좌표를 기준으로 해당 행과 열에 있는 검은색의 갯수를 카운트 해봤더니 위와 같은 결과가 나왔다.

왜인지는 모르겠지만, 우리가 뒤집은 빨간점이 있던 좌표만 홀수이고 나머지는 모두 짝수라는 것을 확인할 수 있다.

일단은 한번 더 해보자.

이번에는 위의 그림에서 빨간색 점을 뒤집어 보자. 그럼 다음과 같은 형태로 맵이 바뀌게 될 것이다.

빨간색 점이 존재했던 판을 뒤집으면서 해당행과 열에 있었던 검은색 판은 흰색판으로, 흰색판은 검은색 판으로 바뀌게 되었다.

그럼 마찬가지로 똑같이 검은색 갯수를 한번 카운트 해보자.

참으로 이상하고도 신기한 결과이다. 딱 봐도 눈에 띄는 숫자는 '5'일 것이다. 왜냐하면 유일하게 홀수인 숫자들이고 동시에

우리가 같이 뒤집었던 2개의 판이기 때문이다.

한번만 더 뒤집어보자.

위의 상태에서 빨간색 점을 뒤집어 보자.

빨간색 점을 뒤집고 검은색 돌의 갯수를 카운트 해서 가져온 결과이다.

이쯤되면 보이겠지만, 정말 신기하게도 "우리가 뒤집은 판만 홀수개" 의 결과를 갖고있다.

사실 본인은 이 정도 해보고 다음과 같은 결론을 내고 구현해서 제출을 해보았다.

1. 모든 좌표를 탐색하면서 검은색 돌의 갯수를 카운트 해준다. (현재 좌표를 기준으로 해당 행과 열의 검은돌의 갯수)

2. 검은 돌의 갯수가 홀수라면 내가 뒤집은 판이고, 그게 아니라면 뒤집은 판이 아니다.

이 부분을 구현할 때, 모든 좌표를 돌면서 돌 때 마다 검은색 돌의 갯수를 카운트 해주는 부분을 간단하게 하기 위해서

입력과 동시에 해당 행과 열에 존재하는 검은색 돌의 갯수를 카운트 해주는 배열을 만들어주었다.

int Garo[], Sero[] 라는 변수인데, Garo[a] = b의 의미는 "a행에 존재하는 돌의 갯수는 b개입니다." 를 의미하고

Sero[a] = b의 의미는 "a열에 존재하는 돌의 갯수는 b개입니다." 를 의미한다.

즉, 우리가 (x, y)에서 돌의 갯수를 카운트 하고 싶다면 간단하게 "Garo[x] + Sero[y]" 를 더해주면 된다.

그런데 !! 여기서 주의를 해줘야 할 것이 하나 있다.

위의 맵을 한번 봐보자. 0 행에 검은색 돌의 갯수 4개, 0열에 검은색 돌의 갯수가 4개가 있기 때문에

(0, 0)에서의 검은색 돌의 갯수를 구하기 위해서 Garo[0] + Sero[0] 을 하게 되면 7이 아닌 8이라는 값이 나오게 된다.

하지만 실제로 카운트 해보면 검은색 돌은 7개 밖에 존재하지 않는다. 즉, 1을 빼줘야 한다는 것인데, 여기서 빼주는 1의 의미는

"겹치는 돌"을 의미한다. Garo[0]은 (0, 0), (0, 1), (0, 2), (0, 3) 이렇게 4개의 돌을 포함하고 있고

Sero[0]은 (0, 0), (1, 0), (2, 0), (3, 0) 이렇게 4개의 돌을 포함하고 있다. 즉 ! (0, 0)이 중복되게 계산 되어지고 있다.

따라서 한번을 빼줘야 한다는 것이다. 반드시 이 과정이 필요한 이유가 N이 짝수이기 때문이다.

그럼 (1, 1)도 한번 보자. (1, 1)에서의 검은색 돌을 구하기 위해서 Garo[1] + Sero[1] 을 하게 되면 2라는 값이 나오게 된다.

왜 이 경우에는 정확하게 2개가 나오는 것일까 ?? 바로 (1, 1)이 검은색 돌이 아닌 하얀색 돌이기 때문이다.

하얀색 돌이기 때문에 중복되서 계산되는 좌표가 존재하지 않게 된다.

즉 ! 모든 맵을 탐색하면서 해당 좌표를 기준으로 해당 행과 열에 존재하는 모든 검은색 돌의 갯수를 구해보자.

그런데 ! 지금 내가 탐색하는 좌표가 검은색 돌이라면, 구한 검은색 돌의 갯수에서 '1'을 빼줘야 하고, 하얀색 돌이라면 '1'을

빼주지 않아도 된다.

위의 방법으로 구한 검은색 돌의 갯수가 홀수개라면, 그 원판은 내가 뒤집은 원판이므로 정답의 갯수++, 짝수라면 뒤집은 원판이

아니기 때문에 정답의 갯수를 건드릴 필요가 없다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, Answer;
char MAP[MAX][MAX];
int Garo[MAX];
int Sero[MAX];
 
void Initialize()
{
    memset(Garo, 0, sizeof(Garo));
    memset(Sero, 0, sizeof(Sero));
    Answer = 0;
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'B')
            {
                Garo[i]++;
                Sero[j]++;
            }
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int Cnt = Garo[i] + Sero[j];
            if (MAP[i][j] == 'B') Cnt--;
            if (Cnt % 2 == 1) Answer++;
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}