백준 2615 - 오목 (C++)

 

현재, 오목에서 승리한 사람이 있는지 탐색하는 문제이다.

오목의 규칙 그대로, 5개의 연속된 바둑알을 놓은 사람이 있는지 판단하고 있다면 이긴 사람을 출력하고, 없다면 0을 출력하면 된다.

문제 풀이

바둑판 위에서 바둑알이 놓여있는 모든 위치에 대해,  5개의 바둑알이 연결되어 있는지를 검사하였다.

 

기본적으로는 이렇게, 8방향에 대해 오목이 5개가 연결되어 있는지를 검사해야 할 것이다.

 

하지만, 꼭 8방향을 다 검사할 필요는 없다.

 

왜냐하면, 모듬 점에 대해서 탐색을 진행하기 때문에, 기준점에서 오른쪽 아래로 검사하는 것은 다른 기준점에서 왼쪽 위를 검사하는 것과 같다. 

 

예를 들어, (1,1) 에서 오른쪽 아래 방향을 검사해서 오목이 나오지 않았다면, (1,1) (2,2) (3,3) (4,4) (5,5)는 연속으로 돌이 놓여있지 않은 상황이다.

 

이 때, 만약 (1,1) (2,2) (3,3)은 검은돌이고, (4,4)는 하얀돌이며 (5,5)는 검은 돌이라고 해보자.

이 때, (5,5)에서 왼쪽 위를 검사하는 것이 의미가 있을까?

 

(5,5)에서 왼쪽 위 방향으로 오목이 만들어져 있다면, 이미 (1,1)에서 탐지한 뒤 검사를 종료했을 것이다.

그러므로 모든 점을 기준으로 오른쪽 아래만 검사하면 된다.

 

동일한 이유로 모든 점에선 우측 상단, 우측, 우측 하단, 하단 이렇게 4방향에 대해서만 검사하면 된다.

 

이 4방향으로만 연속된 바둑알 5개가 놓여있는지 검사하였다.

 

풀이 코드

std::vector<std::vector<int>> Board(19, std::vector<int>(19, 0));
for (int i = 0; i < 19; i++)
{
    for (int j = 0; j < 19; j++)
    {
        std::cin >> Board[i][j];
    }
}

먼저 바둑판의 상태를 입력받았다.

 

for (int i = 0; i < 19; i++)
{
    for (int j = 0; j < 19; j++)
    {
        if (Board[i][j] == 0)
        {
            continue;
        }

        if (Check(Board, j, i) == true)
        {
            std::cout << Board[i][j] << "\n";
            std::cout << i + 1 << " " << j + 1;

            return 0;
        }
    }
}

std::cout << 0;

return 0;

이후, 모든 점에 대해 검사를 하였다. 

바둑알이 놓여있지 않은 점에 대해서는 continue해주었다.

 

만약, 해당 위치에서 오목이 발견되었다면, 해당 위치의 바둑알의 생상과 위치를 출력한 뒤 프로세스를 종료하였으며, 발견되지 않고 반복문들 탈출하였다면 0을 출력하도록 해주었다.

 

bool Check(const std::vector<std::vector<int>>& _Board, int _X, int _Y)
{
    int CurStone = _Board[_Y][_X];

    //우상
    if (!(_X - 1 >= 0 && _Y + 1 < 19 && _Board[_Y + 1][_X - 1] == CurStone))
    {
        int Count = 0;

        for (int i = 0; i < 19; i++)
        {
            int NextX = _X + i;
            int NextY = _Y - i;

            if (NextX >= 19 || NextY < 0)
            {
                break;
            }

            if (_Board[NextY][NextX] == CurStone)
            {
                Count++;
            }
            else
            {
                break;
            }
        }

        if (Count == 5)
        {
            return true;
        }
    }

    //우
    if (!(_X - 1 >= 0 && _Board[_Y][_X - 1] == CurStone))
    {
        int Count = 0;

        for (int i = 0; i < 19; i++)
        {
            int NextX = _X + i;

            if (NextX >= 19)
            {
                break;
            }

            if (_Board[_Y][NextX] == CurStone)
            {
                Count++;
            }
            else
            {
                break;
            }
        }

        if (Count == 5)
        {
            return true;
        }
    }

    //우하
    if (!(_X - 1 >= 0 && _Y - 1 >= 0 && _Board[_Y - 1][_X - 1] == CurStone))
    {
        int Count = 0;

        for (int i = 0; i < 19; i++)
        {
            int NextX = _X + i;
            int NextY = _Y + i;

            if (NextX >= 19 || NextY >= 19)
            {
                break;
            }

            if (_Board[NextY][NextX] == CurStone)
            {
                Count++;
            }
            else
            {
                break;
            }
        }

        if (Count == 5)
        {
            return true;
        }
    }

    //하
    if (!(_Y - 1 >= 0 && _Board[_Y - 1][_X] == CurStone))
    {
        int Count = 0;

        for (int i = 0; i < 19; i++)
        {
            int NextY = _Y + i;

            if (NextY >= 19)
            {
                break;
            }

            if (_Board[NextY][_X] == CurStone)
            {
                Count++;
            }
            else
            {
                break;
            }
        }

        if (Count == 5)
        {
            return true;
        }
    }

    return false;
}

 

Check함수 내부이다.

무식하게 4방향에 대해 모드 반복문을 돌아주었다.

 

코드 전문

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

bool Check(const std::vector<std::vector<int>>& _Board, int _X, int _Y)
{
    int CurStone = _Board[_Y][_X];

    //우상
    if (!(_X - 1 >= 0 && _Y + 1 < 19 && _Board[_Y + 1][_X - 1] == CurStone))
    {
        int Count = 0;

        for (int i = 0; i < 19; i++)
        {
            int NextX = _X + i;
            int NextY = _Y - i;

            if (NextX >= 19 || NextY < 0)
            {
                break;
            }

            if (_Board[NextY][NextX] == CurStone)
            {
                Count++;
            }
            else
            {
                break;
            }
        }

        if (Count == 5)
        {
            return true;
        }
    }

    //우
    if (!(_X - 1 >= 0 && _Board[_Y][_X - 1] == CurStone))
    {
        int Count = 0;

        for (int i = 0; i < 19; i++)
        {
            int NextX = _X + i;

            if (NextX >= 19)
            {
                break;
            }

            if (_Board[_Y][NextX] == CurStone)
            {
                Count++;
            }
            else
            {
                break;
            }
        }

        if (Count == 5)
        {
        return true;
        }
    }

    //우하
    if (!(_X - 1 >= 0 && _Y - 1 >= 0 && _Board[_Y - 1][_X - 1] == CurStone))
    {
        int Count = 0;

        for (int i = 0; i < 19; i++)
        {
            int NextX = _X + i;
            int NextY = _Y + i;

            if (NextX >= 19 || NextY >= 19)
            {
                break;
            }

            if (_Board[NextY][NextX] == CurStone)
            {
                Count++;
            }
            else
            {
                break;
            }
        }

        if (Count == 5)
        {
            return true;
        }
    }

    //하
    if (!(_Y - 1 >= 0 && _Board[_Y - 1][_X] == CurStone))
    {
        int Count = 0;

        for (int i = 0; i < 19; i++)
        {
            int NextY = _Y + i;

            if (NextY >= 19)
            {
                break;
            }

            if (_Board[NextY][_X] == CurStone)
            {
                Count++;
            }
            else
            {
                break;
            }
        }

        if (Count == 5)
        {
            return true;
        }
    }

    return false;
}

int main()
{
    Init();

    std::vector<std::vector<int>> Board(19, std::vector<int>(19, 0));
    for (int i = 0; i < 19; i++)
    {
        for (int j = 0; j < 19; j++)
        {
            std::cin >> Board[i][j];
        }
    }

    for (int i = 0; i < 19; i++)
    {
        for (int j = 0; j < 19; j++)
        {
            if (Board[i][j] == 0)
            {
                continue;
            }

            if (Check(Board, j, i) == true)
            {
                std::cout << Board[i][j] << "\n";
                std::cout << i + 1 << " " << j + 1;

                return 0;
            }
        }
    }

    std::cout << 0;

    return 0;
}