[ 백준 ] 1986 / 체스

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
170/228
post-thumbnail

# Appreciation

/*
 * Problem :: 1986 / 체스
 *
 * Kind :: Simulation
 *
 * Insight
 * - 각 칸에 퀸, 나이트, 폰을 놓아두고
 *   체스판을 순회하다가 빈칸이 아니라 위의 말을 만나면
 *   그 말을 기준으로 주변의 칸의 안전여부를 갱신해주면 된다
 *
 * Point
 * - 퀸과 나이트가 이동할 수 있는 방향을 미리 전역배열로 선언해놓고
 *   이를 적절히 사용하면 하드코딩을 막을 수 있다
 *
 * - 문제에서는 (1,1) 칸부터 시작하지만
 *   편의상 코드에서는 (0,0) 칸부터 시작하도록 하였다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N, M;
char board[1000][1000];
bool isSafe[1000][1000];
int dqy[8] = {-1, -1, -1,  0,  0, +1, +1, +1}; /* 가능한 퀸의 y축 이동방향 */
int dqx[8] = {-1,  0, +1, -1, +1, -1,  0, +1}; /* 가능한 퀸의 x축 이동방향 */
int dky[8] = {-2, -2, -1, -1, +1, +1, +2, +2}; /* 가능한 나이트의 y축 이동방향 */
int dkx[8] = {-1, +1, -2, +2, -2, +2, -1, +1}; /* 가능한 나이트의 x축 이동방향 */

// Set up : Functions Declaration
bool isValid(int y, int x);
void checkQueen(int y, int x);
void checkKnight(int y, int x);
void checkPawn(int y, int x);

int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N >> M;
    memset(board, ' ', sizeof(board));
    int NQ; cin >> NQ;
    for (int i=0; i<NQ; i++) {
        int r, c;
        cin >> r >> c;
        board[r-1][c-1] = 'Q'; /* 문제는 (1,1)~(N,M) 이지만 코드는 (0,0)~(N-1,M-1) */
    }
    int NK; cin >> NK;
    for (int i=0; i<NK; i++) {
        int r, c;
        cin >> r >> c;
        board[r-1][c-1] = 'K'; /* 문제는 (1,1)~(N,M) 이지만 코드는 (0,0)~(N-1,M-1) */
    }
    int NP; cin >> NP;
    for (int i=0; i<NP; i++) {
        int r, c;
        cin >> r >> c;
        board[r-1][c-1] = 'P'; /* 문제는 (1,1)~(N,M) 이지만 코드는 (0,0)~(N-1,M-1) */
    }

    // Process
    memset(isSafe, true, sizeof(isSafe));
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (board[i][j] != ' ') { /* 현재 칸이 빈칸이 아니면 */
                switch (board[i][j]) {
                    /* 현재 칸이 퀸이며 주변칸의 안전여부 갱신 */
                    case 'Q': checkQueen(i, j); break;
                    /* 현재 칸이 나이트이며 주변칸의 안전여부 갱신 */
                    case 'K': checkKnight(i, j); break;
                    /* 현재 칸이 폰이며 주변칸의 안전여부 갱신 */
                    case 'P': checkPawn(i, j); break;
                    default: throw runtime_error("Invalid Value");
                }
            }
        }
    }

    // Control : Output
    int ans = 0; /* 안전한 칸의 개수 */
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (isSafe[i][j]) { ans++; }
        }
    }
    cout << ans << endl;
}

// Helper Functions
bool isValid(int y, int x)
/* 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < N && x >= 0 && x < M;
}

void checkQueen(int y, int x)
/* 현재 칸 (y,x) 에 퀸이 있으며, 이를 기준으로 주변칸의 안전여부 갱신 */
{
    isSafe[y][x] = false; /* 퀸이 존재하는 현재 칸은 안전하지 않음 */
    /* 퀸이 이동할 수 있는 모든 방향으로
     * 장애물(다른 말)을 만나기 전까지 만난 모든 빈칸을
     * 안전하지 않음으로 갱신 */
    for (int i=0; i<8; i++) {
        int ay = y + dqy[i];
        int ax = x + dqx[i];
        while (isValid(ay, ax) && board[ay][ax] == ' ') {
            isSafe[ay][ax] = false;
            ay += dqy[i];
            ax += dqx[i];
        }
    }
}

void checkKnight(int y, int x)
/* 현재 칸 (y,x) 에 나이트가 있으며, 이를 기준으로 주변칸의 안전여부 갱신 */
{
    isSafe[y][x] = false; /* 나이트가 존재하는 현재 칸은 안전하지 않음 */
    /* 나이트가 이동할 수 있는 모든 방향으로 이동 후
     * 만난 빈칸을 안전하지 않음으로 갱신 */
    for (int i=0; i<8; i++) {
        int ay = y + dky[i];
        int ax = x + dkx[i];
        if (isValid(ay, ax) && board[ay][ax] == ' ') {
            isSafe[ay][ax] = false;
        }
    }
}

void checkPawn(int y, int x)
/* 현재 칸 (y,x) 에 폰이 있으며, 이를 기준으로 주변칸의 안전여부 갱신 */
{
    isSafe[y][x] = false; /* 폰이 존재하는 현재 칸은 안전하지 않음 */
    /* 폰은 이동이 불가능하므로 주변 칸의 안전여부에 영향을 미치지 않음 */
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글