[정올] 1733 [백준] 2615 오목

https://www.acmicpc.net/problem/2615

2615번: 오목

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1006&sca=2060 

JUNGOL

 

문제

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

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

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

 

입력

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

 

출력

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

 

 

 

풀이

정올은 틀린 테스트 케이스에 대한 정보를 제공하기 때문에 백준이 익숙하지 않은 분들이
풀이하기에 좋은 사이트라고 생각한다.

미리 바둑판에 대한 정보를 입력 받았기 때문에 바둑돌을 찾을 때마다 5개인지 검증하는 프로그램을 구현하면 된다.

 
bool check(int y, int x, int color) {
    int direction[4][2] = { -1, 1, 0, 1, 1, 1, 1, 0 };
    int count = 1;
 
    for (int i = 0; i < 4; i++){
        int ny = y + direction[i][0];
        int nx = x + direction[i][1];
        count = 1;
        while (1) {
            if (ny < 0 || ny >= 19 || nx < 0 || nx >= 19) break;
 
            if (matrix[ny][nx] == color) {
                count++;
            }
            ny = ny + direction[i][0];
            nx = nx + direction[i][1];
        }
        if (count == 5) {
            answery = y;
            answerx = x;
            return true;
        }
    }
    return false;
}

check 함수를 구현해서 원하는 좌표와 색을 입력으로 준 뒤, 해당 색의 돌이 몇 개 연속으로 나오는지 검증했다.
문제 조건에서 가장 왼쪽, 가장 위의 있는 돌을 기준으로 확인하는 것이기 때문에 8방향이 아니라 4방향만 검증하면 된다. 

 

정올에서 11점만 나왔었는데 디버깅을 통해서 확인해보니 while문 안에 color와 동일할 때 count를 증가시켜주는 부분은 있지만 동일하지 않은 경우에 break하는 부분이 없었다.

 

 

bool check(int y, int x, int color) {
    int direction[4][2] = { -1, 1, 0, 1, 1, 1, 1, 0 };
    int count = 1;
 
    for (int i = 0; i < 4; i++){
        int ny = y + direction[i][0];
        int nx = x + direction[i][1];
        count = 1;
        while (1) {
            if (ny < 0 || ny >= 19 || nx < 0 || nx >= 19) break;
 
            if (matrix[ny][nx] != color) {
                break;
            }
            count++;
            ny = ny + direction[i][0];
            nx = nx + direction[i][1];
        }
        if (count == 5) {
            answery = y;
            answerx = x;
            return true;
        }
    }
    return false;
}

check 함수를 위와 같이 수정했다 색이 동일하지 않은 경우에 break를 하고 아닌 경우에 count를 증가시키는 것이다.

while을 빠져나왔을 때 count가 5가 되면 5목이라고 판단하고 true를 반환해주었다.

 

 이번에도 67점밖에 나오지 않아서 다시 확인해보니 6개 이상의 돌이 존재하는 경우에 1번부터 확인하면 6개라고 판단하지만 2번부터 확인하는 경우에는 5개만 있다고 판단하는 것이 문제였다.

 

bool check(int y, int x, int color) {
    int direction[4][2] = { -1, 1, 0, 1, 1, 1, 1, 0 };
    int count = 1;
 
    for (int i = 0; i < 4; i++){
        int ny = y + direction[i][0];
        int nx = x + direction[i][1];
        count = 1;
        while (1) {
            if (ny < 0 || ny >= 19 || nx < 0 || nx >= 19) break;
 
            if (matrix[ny][nx] != color) {
                break;
            }
            count++;
            ny = ny + direction[i][0];
            nx = nx + direction[i][1];
        }
        if (count == 5) {
            int tempy = y - direction[i][0];
            int tempx = x - direction[i][1];
            if (tempy >= 0 && tempy < 19 && tempx >= 0 && tempx < 19) {
                if (matrix[tempy][tempx] == color) {
                    continue;
                }
            }
            answery = y;
            answerx = x;
            return true;
        }
    }
    return false;
}

그래서 5개가 확인 되었으면 시작 좌표 y, x에서 지금 확인하는 방향과 반대 방향으로 1칸 이동한 뒤
그 위치에 동일한 색의 돌이 있으면 6목 이상이기 때문에 continue를 해주는 것으로 6목을 판단했다.

 

int main(){
    queue<pair<int, int>> bq;
    queue<pair<int, int>> wq;
    int y, x;
    for (int i = 0; i < 19; i++) {
        for (int j = 0; j < 19; j++) {
            cin >> matrix[i][j];
        }
    }
 
    for (int i = 0; i < 19; i++) {
        for (int j = 0; j < 19; j++) {
            if (matrix[i][j] == 1) {
                bq.push({ i, j });
            }
            else if (matrix[i][j] == 2) {
                wq.push({ i, j });
            }
        }
    }

board의 값을 입력받고 검은 돌과 흰돌을 구분하여 queue에 넣어 사전작업을 해주었다.

 

   while (bq.size()) {
        y = bq.front().first;
        x = bq.front().second;
        bq.pop();
        bool temp = check(y, x, 1);
        if (temp) {
            bflag = true;
            break;
        }
    }
 
    while (wq.size()) {
        y = wq.front().first;
        x = wq.front().second;
        wq.pop();
        if (y == 10 && x == 5) {
            int fd = 1;
        }
        bool temp = check(y, x, 2);
        if (temp) {
            wflag = true;
            break;
        }
    }

검은 돌과 흰 돌의 좌표를 queue에서 꺼내가면서 위에서 언급한 check함수를 이용하여 5목이 성립되는지 확인했다.
두 색 모두 성립하는 경우도 있을 수 있기 때문에 플래그를 2개를 이용해서 따로 체크했다.

 

    if ((bflag == true && wflag == true) || (bflag == false && wflag == false)) {
        cout << 0;
    }
    else if (bflag) {
        cout << 1 << endl << answery + 1 << " " << answerx + 1;
    }
    else if (wflag) {
        cout << 2 << endl << answery + 1 << " " << answerx + 1;
    }
 
    return 0;
}

2개의 플래그 값을 이용하여 답을 출력한다.

 

 

전체 코드

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>
 
using namespace std;
int matrix[19][19];
 
bool wflag = false;
bool bflag = false;
int answery, answerx;
 
bool check(int y, int x, int color) {
    int direction[4][2] = { -1, 1, 0, 1, 1, 1, 1, 0 };
    int count = 1;
 
    for (int i = 0; i < 4; i++){
        int ny = y + direction[i][0];
        int nx = x + direction[i][1];
        count = 1;
        while (1) {
            if (ny < 0 || ny >= 19 || nx < 0 || nx >= 19) break;
 
            if (matrix[ny][nx] != color) {
                break;
            }
            count++;
            ny = ny + direction[i][0];
            nx = nx + direction[i][1];
        }
        if (count == 5) {
            answery = y;
            answerx = x;
            return true;
        }
    }
    return false;
}
 
 
int main(){
    queue<pair<int, int>> bq;
    queue<pair<int, int>> wq;
    int y, x;
    for (int i = 0; i < 19; i++) {
        for (int j = 0; j < 19; j++) {
            cin >> matrix[i][j];
        }
    }
 
    for (int i = 0; i < 19; i++) {
        for (int j = 0; j < 19; j++) {
            if (matrix[i][j] == 1) {
                bq.push({ i, j });
            }
            else if (matrix[i][j] == 2) {
                wq.push({ i, j });
            }
        }
    }
 
    while (bq.size()) {
        y = bq.front().first;
        x = bq.front().second;
        bq.pop();
        bool temp = check(y, x, 1);
        if (temp) {
            bflag = true;
            break;
        }
    }
 
    while (wq.size()) {
        y = wq.front().first;
        x = wq.front().second;
        wq.pop();
        if (y == 10 && x == 5) {
            int fd = 1;
        }
        bool temp = check(y, x, 2);
        if (temp) {
            wflag = true;
            break;
        }
    }
 
 
    if ((bflag == true && wflag == true) || (bflag == false && wflag == false)) {
        cout << 0;
    }
    else if (bflag) {
        cout << 1 << endl << answery + 1 << " " << answerx + 1;
    }
    else if (wflag) {
        cout << 2 << endl << answery + 1 << " " << answerx + 1;
    }
 
    return 0;
}

두 사이트 모두 정답으로 나왔다.
처음 PS 문제를 푸는 사람들은 정올을 이용해서 어떤 테스트 케이스에서 문제가 발생하는지 보는 것도 좋은 방법이라고 생각한다.