[백준 2615] 오목

티스토리 뷰

공부/코딩테스트

[백준 2615] 오목

굥굔 2023. 4. 24. 12:25

< 해설 >

다양한 반례처리가 힘들었다. 그리고 사실 제출해서 맞았다고는 안떴는데 여러가지 반례상황을 다 적용시켰고 더이상의 반례는 찾지 못해서 그냥 적는다..

반례는 다음과 같이 적용했다.

6목과 5목이 꼭짓점을 공유하고 있어도 정상적으로 출력되는지
플레이어1과 플레이어2가 둘다 오목을 만족할 때 0을 리턴하는지
가장자리에서 오목이 만족할 때 정상적으로 출력되는지

왼쪽에 있는 돌을 (세로일 경우는 가장 위의 돌 ) 출력해야 하는 조건을 만족하기 위해서

x	x	↗
x	돌의 위치	→
x	↓	↘

로 검사를 진행시켰다. for문으로 19*19 의 인덱스가 0이 아닐시 해당 돌에 대해서 돌이 얼마나 연속으로 놓여있는지에 대해 검사했다. return은 돌이 연속으로 놓아진 개수를 리턴하여 5일시에만 정답으로 처리했다.

이미 검사를 한 돌에 대해서는 이 전 인덱스의 돌이 존재하는지를 따졌다.

이렇게까지 했는데 왜 실패냐 ㅠㅠ

< 문제 >

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.

입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.

입력

출력

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.

< 풀이 >

코드 아래부분에 내가 적용한 테스트케이스들을 넣어뒀다. (수정하면서 사용해서 좀 바뀌었을순 있음)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int Right(int curColor, const int arr[19][19], int x, int y)
{
    int count = 1;
    int nextY = y+1;

    // 전의 바둑돌이 같은색이면 탐색 안함
    if (y != 0)
    {
        if (arr[x][y-1] == curColor)
            return count;
    }

    while (true)
    {
        if (19 < nextY || arr[x][nextY] != curColor)
            break;
        else
        {
            count++;
            nextY++;
        }
    }

    return count;
}

int Down(int curColor, const int arr[19][19], int x, int y)
{
    int count = 1;
    int nextX = x + 1;

    // 전의 바둑돌이 같은색이면 탐색 안함
    if (x != 0)
    {
        if (arr[x-1][y] == curColor)
            return count;
    }

    while (true)
    {
        if (19 < nextX || arr[nextX][y] != curColor)
            break;
        else
        {
            count++;
            nextX++;
        }
    }

    return count;
}

int R_Diag(int curColor, const int arr[19][19], int x, int y)
{
    int count = 1;
    int nextX = x + 1;
    int nextY = y + 1;

    // 전의 바둑돌이 같은색이면 탐색 안함
    if (x != 0 && y != 0)
    {
        if (arr[x - 1][y-1] == curColor)
            return count;
    }

    while (true)
    {
        if (19 < nextX || 19 < nextY || arr[nextX][nextY] != curColor)
            break;
        else
        {
            count++;
            nextX++;
            nextY++;
        }
    }

    return count;
}

int L_Diag(int curColor, const int arr[19][19], int x, int y)
{
    int count = 1;
    int nextX = x - 1;
    int nextY = y + 1;

    // 전의 바둑돌이 같은색이면 탐색 안함
    if (x != 18 && y != 0)
    {
        if (arr[x + 1][y - 1] == curColor)
            return count;
    }

    while (true)
    {
        if ( nextX < 0 || 19 < nextY || (arr[nextX][nextY] != curColor))
            break;
        else
        {
            count++;
            nextX--;
            nextY++;
        }
    }

    return count;
}

int solution(int arr[19][19]) {

    int answer = -1;
    vector<pair<int, pair<int, int>>> winner;

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

            // 오른쪽으로 검사.
            if (Right(arr[i][j], arr, i, j) == 5)
            {
                winner.push_back({ arr[i][j], {i + 1, j + 1 }});
            }

            // 아래로 검사
            if (Down(arr[i][j], arr, i, j) == 5)
            {
                winner.push_back({ arr[i][j], {i + 1, j + 1 } });
            }

            // 왼쪽 대각선검사
            if (L_Diag(arr[i][j], arr, i, j) == 5)
            {
                winner.push_back({ arr[i][j], {i + 1, j + 1 } });
            }

            // 오른쪽 대각선 검사
            if (R_Diag(arr[i][j], arr, i, j) == 5)
            {
                winner.push_back({ arr[i][j], {i + 1, j + 1 } });
            }
        }
    }
    if(winner.size() != 1)
        cout << 0;
    else
    {
        cout << winner[0].first << endl;
        cout << winner[0].second.first << ' ' << winner[0].second.second;
    }

    return answer;
}

int main()
{
    int arr1[19][19] = 
    {
        1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
        1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
        0, 0, 2, 0, 0, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
        1, 1, 1, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
        1, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
        1, 0, 0, 0, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 1, 1, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    }; 
    // 2의 3,3
    // 1의 15,5 둘다 답이므로 0을 리턴

    int arr2[19][19] =
    {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 2, 0, 0, 2, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 2, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 1, 1, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    }; // 답x

    int arr3[19][19] =
    {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2
    }; //2의 19,15 답

    /* 백준용 입력받기 코드 */
    /*int arr[19][19];

    for (int i = 0; i < 19; ++i)
    {
        for (int j = 0; j < 19; ++j)
        {
            int n;
            cin >> n;
            arr[i][j] = n;
        }
    }*/

    solution(arr1);

    return 0;
}

저작자표시 (새창열림)

'공부 > 코딩테스트' 카테고리의 다른 글

[프로그래머스 C++] 정수 삼각형 (0)	2023.04.28
[프로그래머스 C++] 부대복귀 (추가!) (0)	2023.04.27
[프로그래머스 C++] 섬 연결하기 (0)	2023.04.21
[프로그래머스 C++] 구명보트 (0)	2023.04.20
[프로그래머스 C++] 아이템 줍기 (0)	2023.04.17

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2025/06 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

글 보관함

굥굥

티스토리 뷰