K-Queen (feat. 백준, 26006번)

K-Queen
https://www.acmicpc.net/problem/26006

26006번: K-Queen

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, K, KR, KC, QR, QC, t1, t2;
    register int dx[8]{-1, -1, 0, 1, 1, 1, 0, -1}, dy[8]{0, 1, 1, 1, 0, -1, -1, -1};
    map<pair<int, int>, bool> arr;
    cin >> N >> K >> KR >> KC;
    arr[make_pair(KR, KC)] = false;
    for(register int d = 0, nx, ny; d < 8; ++d){
        nx = KR + dx[d], ny = KC + dy[d];
        if(0 < nx && nx <= N && 0 < ny && ny <= N)
            arr[make_pair(nx, ny)] = false;
    }
    for(register int k = 0; k < K; ++k){
        cin >> QR >> QC;
        for(auto& v : arr){
            if(!v.second){
                if(v.first.first == QR)
                    v.second = true;
                else if(v.first.second == QC)
                    v.second = true;
                else{
                    t1 = v.first.first - QR;
                    t2 = v.first.second - QC;
                    if(arr.find(make_pair(QR + t1, QC + t1)) != arr.end())
                        arr[make_pair(QR + t1, QC + t1)] = true;
                    if(arr.find(make_pair(QR + t1, QC - t1)) != arr.end())
                        arr[make_pair(QR + t1, QC - t1)] = true;
                    if(arr.find(make_pair(QR - t1, QC + t1)) != arr.end())
                        arr[make_pair(QR - t1, QC + t1)] = true;
                    if(arr.find(make_pair(QR - t1, QC - t1)) != arr.end())
                        arr[make_pair(QR - t1, QC - t1)] = true;
                    if(arr.find(make_pair(QR + t2, QC + t2)) != arr.end())
                        arr[make_pair(QR + t2, QC + t2)] = true;
                    if(arr.find(make_pair(QR + t2, QC - t2)) != arr.end())
                        arr[make_pair(QR + t2, QC - t2)] = true;
                    if(arr.find(make_pair(QR - t2, QC + t2)) != arr.end())
                        arr[make_pair(QR - t2, QC + t2)] = true;
                    if(arr.find(make_pair(QR - t2, QC - t2)) != arr.end())
                        arr[make_pair(QR - t2, QC - t2)] = true;
                }
            }
        }
    }
    register int check1 = 0, check2 = 0;
    for(auto& v : arr){
        if(v.first.first == KR && v.first.second == KC){
            if(v.second)
                check1 = 1;
        }
        else{
            if(v.second)
                ++check2;
        }
    }
    if(check1){
        if(check2 == (arr.size() - 1))
            cout << "CHECKMATE";
        else
            cout << "CHECK";
    }
    else{
        if(check2 == (arr.size() - 1))
            cout << "STALEMATE";
        else
            cout << "NONE";
    }
    return 0;
}
// *&)*@*

 

반응형

1. N의 범위가 10^9 이므로 2차원 행렬로 계산할 순 없습니다.
2. 따라서 King 위치를 기준으로 Queen의 R,C가 다을 수 있는지를 확인하여 정답을 구해야 합니다.