백준 2615 오목 (C++)

2615번: 오목

완전 탐색을 이용한 문제이다. 이중 반복문으로 모든 좌표에 접근을 하면서 0이 아닌 숫자를 만나게 될 경우 현재 좌표를 기준으로 오목이 완성되는지 확인을 해준다. 대각선 포함 8방향으로 깊이 우선 탐색을 통해 카운트를 해주게 되는데, 탐색 전에 탐색 반대편 방향을 확인해서 만약 같은 돌이 놓여져있다면 이는 탐색 방향으로 오목이 완성되어도 육목, 혹은 그 이상이므로 오목이 아니기 때문에 탐색을 진행하지 않고 다음 방향으로 넘겨준다. 탐색을 진행하면서 카운트가 5가 된다면 오목이 됬다는 것을 의미하고 이 때 탐색 방향으로 육목이 되는지 확인한 후 tf = true를 해준다. 오목이 되었을 때의 돌과 좌표를 출력해주고 만약 오목이 없었다면 0을 출력해주었다. 생각보다 오래 걸린 문제였다. 생각해야할 조건들이 좀 많았다. 구현 문제는 많이 풀어봐야겠다.

#include <iostream>
#include <queue>

using namespace std;

int A[19][19];
bool tf = false;
int dy[8] = { -1, 0, 1, 1, 1, 0, -1,-1 };
int dx[8] = { 1,1,1,0,-1,-1,-1,0 };

void dfs(int a, int b, int count, int d) {
    int ny = a + dy[d];
    int nx = b + dx[d];

    if (count == 5) {
        if ((ny >= 0 && nx >= 0 && ny < 19 && nx < 19) && A[ny][nx] == A[a][b]) {
            return;
        }

        tf = true;
        return;
    }


    if (ny < 0 || nx < 0 || ny >= 19 || nx >= 19) return;
    if (A[ny][nx] != A[a][b]) return;

    dfs(ny, nx, count + 1, d);
}

void solution() {
    for (int i = 0; i < 19; i++) {
        for (int j = 0; j < 19; j++) {
            if (A[j][i] != 0) {
                for (int k = 0; k < 8; k++) {
                    int py = j + dy[(k + 4) % 8];
                    int px = i + dx[(k + 4) % 8];

                    if (A[py][px] == A[j][i]) continue;

                    dfs(j, i, 1, k);
                }

                if (tf) {
                    cout << A[j][i] << endl;
                    cout << j + 1 << " " << i + 1;
                    return;
                }
            }
        }
    }

    cout << 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

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

    solution();

    return 0;
}