6731. 홍익이의 오델로 게임 (삼성 SW Academy, C++)

문제 풀이

 

 게임의 규칙을 찾아야 풀이가 가능한 문제입니다. 게임의 규칙은 다음과 같습니다.

 

1. 같은 곳을 두 번 뒤집으면 결과가 같으므로 이러한 경우는 고려하지 않아도 됩니다.

2. N은 짝수이므로,

2-1) (x, y)의 돌 (=노란색 별) 을 뒤집으면 자기 자신과 가로줄, 세로줄의 돌 색이 바뀌게 되므로 노란색 별 기준 주변의 검은색 돌 갯수는 홀수개가 됩니다.

2-2) 초록색 별 기준 바뀌는 돌의 색은 자기 자신과 자기 자신이 속한 한 줄이 되므로 검은 돌의 갯수는 짝수개가 됩니다.

2-3) 자기 자신의 색이 바뀌지 않는 빨간색 별 기준 바뀌는 돌의 색은 가로 줄 한 개, 세로 줄 한 개이므로 검은 돌의 갯수는 홀수개가 됩니다.

(+ 흰 색 돌을 기준으로 보는 경우 뒤집은 돌의 주변 흰색 돌만 짝수개가 됩니다.)

3. 즉, 가로줄의 검은 돌 갯수와 세로 줄의 검은 돌 갯수를 합한 것이 홀수라면, 뒤집은 돌이 됩니다. (중복 제외)

(+ cin, cout으로 받으면 시간 초과납니다ㅠㅠ)

 

 

코드

 

#include <iostream>
 
using namespace std;
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++)
    {
        int ans = 0;
        char board[1000][1000];
        int h[1000] = { 0, };
        int v[1000] = { 0, };
 
        int n;
        cin >> n;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> board[i][j];
                if (board[i][j] == 'B')
                {
                    h[i]++;
                    v[j]++;
                }
            }
        }
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int x = h[i] + v[j];
                if (board[i][j] == 'B')
                    x -= 1;
 
                if (x % 2 != 0)
                    ans++;
            }
        }
        cout << '#' << tc << ' ' << ans << '\n';
    }
    return 0;
}

 

 

문제 출처

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWefzFeq5P8DFAUh&categoryId=AWefzFeq5P8DFAUh&categoryType=CODE

SW Expert Academy