체스

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
// 1155 ~ 0107
int ans=0;
int Qr[8] = {-1, 1, 0, 0, -1, -1, 1, 1}; 
int Qc[8] = {0, 0, -1, 1, -1, 1, -1, 1};
int Kr[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int Kc[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int N,M,Q,K,P;
char board[1005][1005]; // 1 ~ 1000 사용
int vis[1005][1005]; // 1 ~ 1000 사용
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    queue<pair<pair<int,int>,char>> q;
    cin >> N >> M;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            board[i][j] = '.';
    cin >> Q;
    for(int i=0;i<Q;i++)
    {
        int r,c;
        cin >> r >> c;
        board[r][c] = 'Q';
        q.push({{r,c},'Q'});
        vis[r][c] = true;
    }
    cin >> K;
    for(int i=0;i<K;i++)
    {
        int r,c;
        cin >> r >> c;
        board[r][c] = 'K';
        q.push({{r,c},'K'});
        vis[r][c] = true;
    }
    cin >> P;
    for(int i=0;i<P;i++)
    {
        int r,c;
        cin >> r >> c;
        board[r][c] = 'P';
        vis[r][c] = true;
    }
    // Queen이 먼저 수행한 뒤에 Knight가 수행해야 함 (반대가 되면 더 갈 수 있는데 막히는 경우가 생김)
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        if(cur.second == 'Q'){
            for(int dir=0;dir<8;dir++)
            {
                int nr = cur.first.first;
                int nc = cur.first.second;
                while(true)
                {
                    nr += Qr[dir];
                    nc += Qc[dir];
                    if(nr<1 or nc<1 or nr>N or nc>M) break;
                    if((vis[nr][nc] != 0 and vis[nr][nc] != 1) or board[nr][nc] != '.') break;
                    vis[nr][nc] = 1;
                }
            }
        }else{
            for(int dir=0;dir<8;dir++)
            {
                int nr = cur.first.first + Kr[dir];
                int nc = cur.first.second + Kc[dir];
                if(nr<1 or nc<1 or nr>N or nc>M) continue;
                if(vis[nr][nc] > 0 or board[nr][nc] != '.') continue;
                vis[nr][nc] = 2;
            }
        }
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            if(vis[i][j] == 0) ans++;
    cout << ans;
    return 0;
}

• 주의할 점
  • 반드시 Knight보다 Queen이 먼저 수행되어야 한다 (더 많이 갈 수 있기 때문)
  • 같은 Queen끼리 방문한 점은 Queen이 다시 방문할 수 있어야 한다!
    --> 만약 방문하지 못하면 퀸의 실행 순서에 따라 방문하지 못하는 점이 발생!
    --> vis[r][c]를 bool로 하면 안됨...ㅠㅠ