[SWEA] 11315 오목 판정

문제

SWEA 11315 : 오목 판정

SW Expert Academy

접근

 BFS를 통해 돌이 놓인 위치에서 갈 수 있는 모든 방향으로 전진하며 돌의 개수를 세 주었다. 이때 문제 제목에 오목이라고 쓰여있어서 연속되는 돌의 개수가 5개여야 하는 것으로 착각할 수 있지만, 문제의 조건을 보면 연속하는 돌의 개수가 다섯 개 이상이면 "YES"이다. 따라서 BFS를 돌 때 counter의 수가 5이상이면 break를 하고 "YES"를 출력해주면 된다.

코드

#include <iostream>
#include <queue>

#define endl "\n"

using namespace std;

struct qnum {
    int x, y, go, counter;
};

int main() {
    int test_case, dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    cin >> test_case;
    for (int t = 1; t <= test_case; t++) {
        int n, chk = 0;
        char map[25][25];
        cin >> n;
        queue<qnum> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
                if (map[i][j] == 'o') {
                    q.push({i, j, 0, 1});
                    q.push({i, j, 1, 1});
                    q.push({i, j, 2, 1});
                    q.push({i, j, 3, 1});
                    q.push({i, j, 4, 1});
                    q.push({i, j, 5, 1});
                    q.push({i, j, 6, 1});
                    q.push({i, j, 7, 1});
                }
            }
        }
        while (!q.empty()) {
            qnum f = q.front();
            q.pop();
            if (f.counter >= 5) {
                chk = 1;
                break;
            }
            int newx = f.x + dx[f.go];
            int newy = f.y + dy[f.go];
            if (newx >= 0 && newx < n && newy >= 0 && newy < n && map[newx][newy] == 'o')
                q.push({newx, newy, f.go, f.counter + 1});
        }
        cout << "#" << t << " ";
        if (chk == 0)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study