[ 백준 16955 ] 오목, 이길 수 있을까 ? (C++)

백준의 오목, 이길 수 있을까?(16955) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 빈 칸에 'X' 하나의 돌을 더 놓아서 게임을 이길 수 있는지 판단만 하면 되는 문제였다.

   그래서 본인은, 입력과 동시에 'X'가 위치한 좌표들을 Vector에 저장해 주었다.

   이 후, 해당 좌표들을 하나씩 탐색해 보았다.

   탐색하는 내용은 다음과 같다.

   "해당 좌표로부터 8방향을 모두 탐색하는데, 한 방향당 4개의 칸을 더 확인했을 때, 'X'의 갯수가 4개이고, '.'의 갯수가

    1개" 라면 게임을 이길 수 있다고 판단하여 끝내주었다.

   'X'가 존재하는 좌표라면, 이미 'X'의 갯수가 1개일 것이고 특정 방향으로 4칸을 더 탐색했을 때, 'X'가 3개 더 있어서,

   총 'X'가 4개가 되고, 빈 칸이 하나 있다면, 이는 그 빈 칸에 돌을 놓으면 승리할 수 있기 때문이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
char MAP[MAX][MAX];
vector<pair<int, int>> V;
 
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
void Input()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'X') V.push_back(make_pair(i, j));
        }
    }
}
 
bool Game(int x, int y)
{
    for (int i = 0; i < 8; i++)
    {
        int nx, ny, Cnt, Empty;
        Cnt = 1;
        Empty = 0;
        nx = x;
        ny = y;
        for (int j = 0; j < 4; j++)
        {
            nx = nx + dx[i];
            ny = ny + dy[i];
            if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX)
            {
                if (MAP[nx][ny] == 'X') Cnt++;
                if (MAP[nx][ny] == '.') Empty++;
            }
        }
        if (Cnt == 4 && Empty == 1) return true;
    }
    return false;
}
 
void Solution()
{
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
 
        if (Game(x, y) == true)
        {
            cout << 1 << endl;
            return;
        }
    }
    cout << 0 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}