백준 23353번: 승부 조작

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

23353번: 승부 조작

각 좌표를 포함하면서 연속으로 존재하는 흑돌의 길이를 흑돌의 방향(가로, 세로, 대각선)별로 분류하여 저장한다면, 어느 한 백돌을 흑돌로 바꿨을 때 백돌의 주변에 존재하는 흑돌을 포함하는 연속된 흑돌의 길이는 O(1)번만에 계산할 수 있으므로, 각 백돌을 흑돌로 바꿨을 때 갱신되는 흑돌의 길이는 각 방향으로 백돌 앞뒤의 연속 흑돌 길이의 합 + 1로 빠르게 계산할 수 있다.

#include <iostream>
#include <queue>

using namespace std;

// 각 백돌의 좌표 (y, x)를 pair로 저장해 큐에 push
typedef pair<int, int> coord;
typedef queue<coord> que;

#define MAX_N 1000

// dir 방향으로 다음 칸의 방향을 매크로를 이용해 계산
#define dY add[dir][0]
#define dX add[dir][1]
// NOW, PREV, POST: 각각 dir 방향으로 현재 좌표, 이전 좌표, 다음 좌표의 연속값
#define NOW score[dir][y][x]
#define PREV score[dir][y - dY][x - dX]
#define POST score[dir][y + dY][x + dX]

//0: 세로
//1: 가로
//2: 기울기 1 대각
//3: 기울기 -1 대각

// N: 게임판의 크기, ans: 최장 연속 흑돌의 길이
// ans: { 가로, 세로, 기울기 1 대각선, 기울기 -1 대각선}[dir]방향 변위
int N, ans = 0, add[4][2] = { {1, 0}, {0, 1}, {1, 1}, {1, -1} };
// board: 냥목 게임판
// score[dir][y][x]: 게임판에서 좌표 (y, x)를 포함한 dir 방향의 연속된 흑돌의 길이
short board[MAX_N][MAX_N], score[4][MAX_N][MAX_N];

int max(int a, int b) { return a > b ? a : b; }

// 좌표 (y, x)가 바둑판 위에 존재한다면 true, 아니라면 false
bool is_valid(int y, int x) { return y >= 0 && y < N&& x >= 0 && x < N; }

// 좌표 (y, x)를 포함하는 dir 방향의 연속된 흑돌의 길이를 반환
int set_score(int dir, int y, int x) {
    // 아직 흑돌의 길이를 계산하지 못했다면
    if (!NOW) {
        // 이전 좌표가 존재하는 좌표값이라면 현재 연속값을 아래와 같이 설정한다
        // 현재 좌표에 흑돌이 있다면 이전까지의 연속값 + 1,
        //                   없다면 0
        if (is_valid(y - dY, x - dX)) 
            NOW = board[y][x] == 1 ? PREV + 1 : 0;
        // 만일 연속값이 0이 아니고 다음 좌표가 존재한다면
        // 다음 값을 재귀적으로 계산한 뒤 현재값과 비교해
        // 더 큰 값을 현재 연속값으로 갱신
        if (NOW && is_valid(y + dY, x + dX))
            NOW = max(NOW, set_score(dir, y + dY, x + dX));
    }
    // 이전에 계산한 흑돌의 길이와 현재 흑돌의 길이를 비교
    ans = max(ans, NOW);
    // 계산된 흑돌의 길이를 반환
    return NOW;
}

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // y, x: 각 좌표, chk: 백돌을 흑돌로 바꿨을 때 갱신된 흑돌의 연속값
    int y, x, chk;
    // q: 백돌의 좌표의 집합
    que q;

    // 게임판의 상태를 입력받으면서 백돌의 좌표를 q에 push
    cin >> N;
    for (y = 0; y < N; y++) for (x = 0; x < N; x++) {
        cin >> board[y][x];
        if (board[y][x] == 2) q.push({ y, x });
    }

    // 게임판의 좌우 및 위쪽 모서리의 초기 연속값틀 해당 좌표의 흑돌이 있는지로 설정
    for (int i = 0; i < N; i++) {
        score[1][i][0] = score[2][i][0] = (board[i][0] == 1);
        score[0][0][i] = score[2][0][i] = score[3][0][i] = (board[0][i] == 1);
        score[3][i][N - 1] = (board[i][N - 1] == 1);
    }

    for (int i = 0; i < N; i++) {
        // 가로 및 세로 연속값을 계산
        for (int j = 1; j < N; j++) {
            set_score(0, j, i);
            set_score(1, i, j);
        }

        // 기울기가 1인 흑돌의 연속값을 계산
        for (int j = 1; i + j < N; j++) {
            set_score(2, i + j, j);
            set_score(2, j, i + j);
        }

        // 기울기가 -1인 흑돌의 연속값을 계산
        for (int j = 1; i + j < N; j++) {
            set_score(3, j, N - 1 - i - j);
            set_score(3, i + j, N - 1 - j);
        }
    }

    // 모든 백돌에 대해
    while (!q.empty()) {
        // 백돌의 좌표를 q에서 가져온 뒤
        coord c = q.front();
        q.pop();

        // 매크로를 위해 변수 y, x에 저장
        y = c.first; x = c.second;
        // 각 방향에 대해
        for (int dir = 0; dir < 4; dir++) {
            // 백돌을 흑돌로 바꾸었으므로 연속값의 최솟값은 반드시 1
            chk = 1;
            // 이전 좌표값과 다음 좌표값이 존재한다면 해당 연속값을 더한다
            if (is_valid(y - dY, x - dX)) chk += PREV;
            if (is_valid(y + dY, x + dX)) chk += POST;
            // 최댓값 갱신
            ans = max(ans, chk);
        }
    }

    // 가장 큰 연속된 흑돌의 길이를 출력
    cout << ans << '\n';

    return 0;
}