백준 2615 오목

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

#include <iostream>
#include <vector>

using namespace std;


vector<vector<int>> board(22, vector<int>(22, 0));

//하, 우, 우하대각선, 우상대각선 순
int ny[4] = {1, 0, 1, -1};
int nx[4] = {0, 1, 1, 1};

int main() {


    for (int i = 1; i <= 19; i++) {
        for (int j = 1; j <= 19; j++) {
            cin >> board[i][j];
        }
    }


    for (int i = 1; i <= 19; i++) {
        for (int j = 1; j <= 19; j++) {


            //현재 위치에 바둑돌이 있다면
            if (board[i][j]) {

                int cur = board[i][j];


                //방향
                for (int k = 0; k < 4; k++) {
                    int l = 1;  //현재 위치로부터 해당 방향의 같은 돌의 개수
                    int newY, newX;
                    //[i][j] 바둑돌로부터의 거리
                    while (1) {

                        newY = i + ny[k] * l;
                        newX = j + nx[k] * l;

                        //해당 위치가 바둑판의 범위를 넘어가는지 확인
                        if (newY < 1 || newY > 19 || newX < 1 || newX > 19) {
                            break;
                        } else if (cur != board[newY][newX]) {
                            break;
                        }

                        l++;

                    }

                    if (l == 5) {
                        if ((i - ny[k] < 1 || i - ny[k] > 19) || (j - nx[k] < 1 || j - nx[k] > 19)) {
                            cout << cur << "\n";
                            cout << i << " " << j << "\n";
                            return 0;
                        } else if (board[i - ny[k]][j - nx[k]] != cur) {
                            cout << cur << "\n";
                            cout << i << " " << j << "\n";
                            return 0;
                        }
                    }
                }
            }
        }
    }

    cout << 0;

    return 0;
}

1. 문제

 현재진행중인 오목 판과 그 위의 바둑돌의 현황이 주어진다. 6목 이상은 허용하지 않는다고 했을 때, 오목의 승패 여부, 판가름났을 경우 승자와 승리 조건에 해당하는 바둑돌 중 가장 좌측에 있는 바둑돌의 위치를 출력한다.

2. 풀이

브루트포스인데 고려해야 할 점이 좀 많았다. 우선 바둑돌을 셀 수 있는 방향은 여덟방향이다. 그 중 오목이 성립되었을 때, 첫 번째 돌의 위치가 가장 좌측에 있는 경우는 우, 우하, 하, 우상으로 네 가지이다. 이 방향을 배열에 입력해준다.

//하, 우, 우하대각선, 우상대각선 순
int ny[4] = {1, 0, 1, -1};
int nx[4] = {0, 1, 1, 1};

 

바둑돌을 입력받고 오목판의 모든 위치에 대해 계산을 진행한다.

 //현재 위치에 바둑돌이 있다면
            if (board[i][j]) {

                int cur = board[i][j];


                //방향
                for (int k = 0; k < 4; k++) {
                    int l = 1;  //현재 위치로부터 해당 방향의 같은 돌의 개수
                    int newY, newX;
                    //[i][j] 바둑돌로부터의 거리
                    while (1) {

                        newY = i + ny[k] * l;
                        newX = j + nx[k] * l;

                        //해당 위치가 바둑판의 범위를 넘어가는지 확인
                        if (newY < 1 || newY > 19 || newX < 1 || newX > 19) {
                            break;
                        } else if (cur != board[newY][newX]) {
                            break;
                        }

                        l++;

                    }

현재 위치에 바둑돌이 존재한다면(1, 2) 위치를 잡고, 위에서 정의한 각 방향에 대해 연속된 같은 바둑돌의 개수를 구하면서 따라간다. 가다가 연속이 끊기면 무한루프를 빠져나온다.

		if (l == 5) {
                        if ((i - ny[k] < 1 || i - ny[k] > 19) || (j - nx[k] < 1 || j - nx[k] > 19)) {
                            cout << cur << "\n";
                            cout << i << " " << j << "\n";
                            return 0;
                        } else if (board[i - ny[k]][j - nx[k]] != cur) {
                            cout << cur << "\n";
                            cout << i << " " << j << "\n";
                            return 0;
                        }
                    }

여기서 애를 좀 많이 먹었다. 만약 각 방향으로 수를 세어 확인한게 5개일 경우 출력하기 전에 확인해야 할 사항이 하나 더 있다. 

해당 위치에서 확인할 경우 우측으로 오목 조건을 만족했다고 바로 출력하면 6목을 고려할 수 없는 문제가 생긴다. 이를 해결하기 위해 나아갔던 방향의 반대방향 위치의 하나를 확인한다. 

 그 위치가 오목판을 벗어나거나, 벗어나지 않았는데 다른 바둑돌이거나 비어있을 경우 오목이 확정이므로 승리 여부와 해당 돌의 위치를 출력한다.

 

 모든 범위를 돌았는데도 오목이 발견되지 않으면 0을 출력하면 정답을 구할 수 있다.