[Algorithm] Programmers :: 혼자서 하는 틱택토

https://school.programmers.co.kr/learn/courses/30/lessons/160585

프로그래머스

struct Node
{
    int y;
    int x;
};
 
int dir[4][2][2] = { {{-1,0},{1,0}}, {{0,-1},{0,1}}, {{-1,-1},{1,1}}, {{-1,1},{1,-1}} };
vector<vector<Node>> nodes(2);
char targets[2] = { 'O', 'X' };
 
bool check(char target, vector<string>& board)
{
    int targetIndex = target == 'O' ? 0 : 1;
 
    for (int i = 0; i < nodes[targetIndex].size(); ++i)
    {
        int curY = nodes[targetIndex][i].y;
        int curX = nodes[targetIndex][i].x;
 
        for (int j = 0; j < 4; ++j) // 상하, 좌우, 대각 두개
        {
            int count = 2;
            int answerCount = 2;
 
            for (int k = 0; k < 2; ++k)
            {
                int tempY = curY;
                int tempX = curX;
 
                while (count != 0)
                {
                    int nextY = tempY + dir[j][k][0];
                    int nextX = tempX + dir[j][k][1];
 
                    if (nextY < 0 || nextY >= 3) break;
                    if (nextX < 0 || nextX >= 3) break;
 
                    if (board[nextY][nextX] == targets[targetIndex])
                    {
                        --answerCount;
                        tempY = nextY;
                        tempX = nextX;
                    }
 
                    --count;
                }
            }
 
            if (answerCount == 0) return true;
        }
    }
 
    return false;
}
 
int solution(vector<string> board)
{
    int answer = -1;
 
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            if (board[i][j] == 'O') nodes[0].push_back({ i,j });
            else if (board[i][j] == 'X')nodes[1].push_back({ i,j });
        }
    }
 
    int oCount = nodes[0].size();
    int xCount = nodes[1].size();
 
    if (abs(oCount - xCount) >= 2) return 0; // O이랑 X가 2개 이상차이나면 안되고
    if (nodes[1].size() > nodes[0].size()) return 0; // X이 O보다 많으면 안됨.
 
    bool isWinO = check('O', board);
    bool isWinX = check('X', board);
 
    if (oCount == xCount)
    {
        if (isWinO) return 0;
    }
    else
    {
        if (isWinX) return 0;
    }
 
    return 1;
}

보드크기가 3x3밖에 안되기 때문에, 그냥 완전하드코딩해도 되는 문제긴 하다.

다만, 이 문제의 경우에는 작지만 만약 보드크기가 10x10이라던가 100x100일 경우를 고려해서 코드를 짜 봤다.

보드판에서 O와 X의 위치들을 저장한다음 이후에 하나씩 돌면서 상하,좌우,대각 2개를 검사한다.

검사해야할 방향이 더 있으면 dir에 추가하면 끝이고 보드크기가 크면 check함수의 k값을 늘리면 끝이다.

 

문제 규칙은 다음과 같다.

보드판이 주어질 경우, 해당보드판이 적절한지 아닌지 판단하는 것이다.

예를들어 O가 1개, X가 3개가 있다고 가정하자. 틱택토는 O와 X가 번갈아가면서 놓이기 때문에 절대로 올 수 없는 상황이니 0을 리턴해야한다. 

그러면 다음과 같이 정리된다.

 

1. O랑 X의 개수차이의 절대값은 2개이상 차이나면 안된다

        -> 번갈아가면서 놓이기 때문에 2개이상 차이날 수가 없다.

 

2. X는 절대로 O의 개수를 초과할 수 없다.

        -> O부터 시작해서 번갈아가면서 놓기때문에 X가 O의 개수를 초과할 수 없다.

 

3. O와 X의 개수가 같을 때, O가 이겨있으면 안된다.

        -> O가 이긴순간 게임은 끝이기 때문에, X는 O보다 1개가 더 적어야 한다. (게임이 끝난다음 놓을 수 없으니까)

 

4. O가 X보다 1개 더 많을 때, X가 이겨있으면 안된다.

        -> X가 이긴순간 게임 끝나야 하기 때문에, O가 더 많을수가 없다. (게임이 끝난다음 놓을 수 없으니까)

 

 

대략 위 규칙을 생각하고 문제풀었는데 다행히 한번에 풀렸다.

다만 내 코드같은 경우 최적화의 여지가 더 있긴하다. 같은 방향검사에 대해서 만난 같은 말(O나 X)에 대해서, 만날때마다 임시컨테이너에 저장했다가 최종적으로 해당방향으로 검사가 실패로 끝날 경우 임시컨테이너에 있는 얘들에 대해서도 해당방향으로는 실패했다고 기록해두는 것이다.

물론 이번문제같이 보드크기가 작으면 상관없긴한데 보드크기가 크면 고려해볼수도 있다. 대신 메모리는 더 사용해야겠지만.