[ SWEA 4615 ] 재미있는 오셀로 게임 (C++)

 

SWExpertAcademy의 재미있는 오셀로 게임(4615 / D3) 문제이다.

[ 문제풀이 ]

1) 먼저 오셀로 게임에 대해서 정확하게 이해하고 가보도록 하자.

   ( 게임에 대해서 완벽하게 이해하신 분들은 2)번 구현설명으로 바로 넘어가셔도 됩니다 ! )

   문제의 예제입력으로 주어진 값들로 왜 결과과 0 16이 나오는지 알아보자.

  

   맵의 초기상태이다. 이 상태에서 입력의 순서대로 입력을 한번 해보자.

   (1, 2)에 흑돌을 놓아보면 다음과 같아진다.

  

   그런데 게임 규칙 상, (1, 2)에 놓아진 흑돌 때문에 빨강색으로 표시된 백돌은 파랑색으로 표시된 2개의 흑도 사이에 끼이게

   되므로 빨강색 백돌은 흑돌이 되어진다.

   즉, 이와 같은 상태가 되어진다.

   이 후, (1, 1)에 백돌을 놓아보자.

   (1, 1)에 놓은 백돌 때문에 빨강색으로 표시된 흑돌은, 파랑색으로 표시된 백돌 2개 사이에

   끼이게 되므로 백돌로 바뀌게 된다.

   즉, 이와 같은 상태가 되어진다.

   이 후, (4, 3)에 흑돌을 놓아보자.

   위와 같은 원리로, 빨강색으로 표시된 백돌은 흑돌이 되어진다.

   이런 식으로 게임을 진행해 나가다가 게임이 종료되었을 때 맵 위에 있는 흑돌의 백돌의 갯수를 구하면 된다.

   그리고 게임의 룰에 의하면, 돌을 놓을 곳이 없다면 상대편 플레이어가 다시 돌을 놓는다고 되어있는데, 입력조건에

   보면, 돌을 놓을 수 없는 곳은 주어지지 않는다고 했으므로 이 조건을 구현할 때 생각하지 않아도 될 것 같다.

2) 이제 본격적인 구현에 들어가보자.

   우리는 돌을 놓는 곳의 좌표를 입력으로 입력받게 된다. 이 후에 우리가 해줘야 할 일에 대해서 정리를 해보자.

   1. 해당 좌표를 기준으로 총 8방향(↖, ↑, ↗, ←, →, ↙, ↓, ↘) 을 쭉 탐색해준다.

      여기서 쭉 이라는 것은 바로 옆 한칸만이 아닌, 또 다른 조건에 부합할 때 까지 탐색을 한다는 의미이다.

      그럼 또다른 조건에는 뭐가 있을지 알아보자.

      1) 맵의 범위를 벗어나는 경우

      - 맵의 범위를 벗어나는 경우이면 탐색을 더 이상 할 수가 없다.

      2) 같은 색깔의 돌이 나왔는데, 그 전에 다른 색깔의 돌이 나오지 않은 경우

         예를 들면 다음과 같은 경우이다.

    

      위의 맵에서, "여기" 라고 표시된 곳에, W(백돌)을 놓는 경우를 생각해보자. 위로 탐색하게 되면 위에 있는

      흑돌이 색깔이 바뀌겠지만, 오른쪽 방향으로 탐색하는 경우를 살펴보자.

      같은 색깔이 돌이 나왔지만, 그 전에 다른 색깔의 돌이 나오지 않은 경우 맵에서 변하는 것은 없다.

      3) 같은 색깔의 돌이 나왔는데, 그 전에 다른 색깔의 돌이 나온 경우

      - 가운데 끼인 다른 색깔의 돌을 바꿔줘야 하는 상황이다.

        중요한 것은, 탐색을 중단해야 한다는 것이다.

            

        위의 상황에서 "여기"에 W(백돌)을 놓는 경우를 생각해보자.

        파랑색 'B'가 'W'사이에 끼이게 되므로 'W'로 바뀌게 될 것이다. 그럼 빨강색 'B'는 어떻게 될까 ??

        빨강색 'B'는 변하지 않는다.

        하지만, 탐색을 중단하지 않고 계속 한다고 생각해보면, "여기"에 놓여진 'W'와 빨강색 'B'의 오른쪽 옆에 있는

        'W'에 의해서 빨강색 'B'의 값 또한 바뀌게 될 수도 있다. 따라서 탐색을 중단해줘야 한다.

       4) 빈 공간을 만났을 경우

       - 더 이상 탐색을 할 필요가 없다. 빈 공간이 만나면 탐색을 종료해주면 된다.

       

3) 위의 상황들을 8방향을 탐색하면서, 구현해 주기만 하면 된다.

   최종적으로, 게임이 끝난 후 맵을 탐색하면서 백돌과 흑돌의 갯수를 카운트 하면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
pair<int, int> Answer;
vector<pair<pair<int, int>, int>> V;
 
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
void Initialize()
{
    memset(MAP, 0, sizeof(MAP));
    V.clear();
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int y, x, c;
        cin >> y >> x >> c;
        y--; x--;
        V.push_back(make_pair(make_pair(x, y), c));
    }
    MAP[N / 2][N / 2] = 2;
    MAP[(N / 2) - 1][(N / 2) - 1] = 2;
    MAP[(N / 2) - 1][N / 2] = 1;
    MAP[N / 2][(N / 2) - 1] = 1;
}
 
void Ocelo(int x, int y, int Color)
{
    MAP[x][y] = Color;
 
    for (int i = 0; i < 8; i++)
    {
        bool Flag = false;
        for (int k = 1; k < 8; k++)
        {
            int nx = x + dx[i] * k;
            int ny = y + dy[i] * k;
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) break;
            if (MAP[nx][ny] == 0) break;
            if (MAP[nx][ny] == Color && Flag == false) break;
            
            if (MAP[nx][ny] != 0 && MAP[nx][ny] != Color) Flag = true;
            if (MAP[nx][ny] == Color)
            {
                while (1)
                {
                    if (nx == x && ny == y) break;
                    nx = nx - dx[i];
                    ny = ny - dy[i];
                    MAP[nx][ny] = Color;
                }
                break;
            }
        }        
    }
}
 
bool Is_Full()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == 0) return false;
        }
    }
    return true;
}
 
pair<int, int> Count()
{
    int Black, White;
    Black = White = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == 1) Black++;
            else if (MAP[i][j] == 2) White++;
        }
    }
    return{ Black, White };
}
 
void Solution()
{
    for (int i = 0; i < V.size(); i++)
    {
        if (Is_Full() == true) break;
 
        int x = V[i].first.first;
        int y = V[i].first.second;
        int C = V[i].second;
 
        Ocelo(x, y, C);
    }
    Answer = Count();
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer.first << " " << Answer.second << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}