C++로 N개의 나이트가 있는 변형된 체스판에서 킹의 유효한 이동 가능 여부 확인하기

무한히 넓은 체스판 위에서 일반 체스와 동일한 규칙이 적용된다고 가정해 봅시다. 이때 체스판 위에 배치된 N개의 나이트 좌표(-10^9 ≤ x, y ≤ 10^9)와 킹의 좌표가 주어졌을 때, 킹이 더 이상 유효한 이동을 할 수 없는 상태, 즉 체크메이트인지 확인하는 것이 이 문제의 목표입니다.

입력 및 출력 예시

입력 1

a1[] = { { 2, 1 }, { 1, 3 }, { 3, 6 }, { 5, 5 }, { 6, 1 }, { 7, 3 } }, king -> {4, 3}

출력 1

Yes

킹이 체크메이트 상태이기 때문에 어떤 이동도 할 수 없습니다.

입력 2

a1[] = {{1, 1}}, king -> {3, 4}

출력 2

No

킹이 유효한 이동을 할 수 있는 상태입니다.

접근 방법

나이트는 체스 기물 중에서도 독특한 이동 방식을 가집니다. 가로로 두 칸, 세로로 한 칸, 또는 세로로 두 칸, 가로로 한 칸 움직이며, 전체적인 이동 경로가 알파벳 "L"자 모양을 이룹니다. 따라서 나이트 하나당 최대 8가지의 이동이 가능합니다.

이러한 특성을 활용하면 문제를 효율적으로 해결할 수 있습니다. 먼저 pair를 키로 사용하는 맵(hash map)을 만들어, 각 나이트가 공격할 수 있는 모든 좌표를 표시합니다. 그다음 킹의 인접한 8개 좌표를 하나씩 검사합니다.

• 검사한 좌표 중 단 하나라도 나이트의 공격 범위 밖이라면, 킹은 그 칸으로 이동할 수 있으므로 체크메이트가 아닙니다.
• 반대로 8개 좌표가 모두 나이트의 공격 범위 안에 있다면, 킹은 어디로도 이동할 수 없으므로 체크메이트로 판정합니다.

맵을 사용하는 경우 시간 복잡도는 O(N log N)이며, unordered_map을 사용하면 평균적으로 O(N)까지 줄일 수 있습니다.

C++ 구현 예제

// C++ 프로그램: 변형된 체스판에 N개의 나이트가 있을 때
// 킹이 유효한 이동을 할 수 있는지 확인합니다.
#include <bits/stdc++.h>
using namespace std;

bool checkCheckMate1(pair<int, int> a1[], int n1, int kx1, int ky1) {
    // 나이트가 공격할 수 있는 좌표를 표시하기 위한 맵
    map<pair<int, int>, int> mpp1;

    // 주어진 N개의 나이트에 대해 반복
    for (int i = 0; i < n1; i++) {
        int x = a1[i].first;
        int y = a1[i].second;

        // 나이트가 도달할 수 있는 "L"자 모양의 모든 좌표를 표시
        mpp1[{ x, y }] = 1;          // 현재 위치
        mpp1[{ x - 2, y + 1 }] = 1;  // 1번째 이동
        mpp1[{ x - 2, y - 1 }] = 1;  // 2번째 이동
        mpp1[{ x + 1, y + 2 }] = 1;  // 3번째 이동
        mpp1[{ x + 1, y - 2 }] = 1;  // 4번째 이동
        mpp1[{ x - 1, y + 2 }] = 1;  // 5번째 이동
        mpp1[{ x + 2, y + 1 }] = 1;  // 6번째 이동
        mpp1[{ x + 2, y - 1 }] = 1;  // 7번째 이동
        mpp1[{ x - 1, y - 2 }] = 1;  // 8번째 이동
    }

    // 킹 주변의 가능한 8개 좌표에 대해 반복
    for (int i = -1; i < 2; i++) {
        for (int j = -1; j < 2; j++) {
            int nx = kx1 + i;
            int ny = ky1 + j;

            // 킹의 현재 위치는 제외
            if (!(i == 0 && j == 0)) {
                // 해당 칸으로 이동이 가능한지 확인
                if (!mpp1[{ nx, ny }]) {
                    return true;   // 유효한 이동 존재 → 체크메이트 아님
                }
            }
        }
    }

    // 어떤 방향으로도 이동할 수 없음 → 체크메이트
    return false;
}

// 드라이버 코드
int main() {
    pair<int, int> a1[] = { { 2, 1 }, { 1, 3 }, { 3, 6 }, { 5, 5 }, { 6, 1 }, { 7, 3 } };
    int n1 = sizeof(a1) / sizeof(a1[0]);
    int x = 4, y = 3;

    if (checkCheckMate1(a1, n1, x, y))
        cout << "Not Checkmate!";
    else
        cout << "Yes its checkmate!";

    return 0;
}

실행 결과

Yes its checkmate!

예제에서 6개의 나이트가 킹({4, 3}) 주변의 8개 칸을 모두 공격하고 있으므로, 킹은 유효한 이동을 할 수 없으며 프로그램은 체크메이트임을 출력합니다. 이처럼 맵 하나만으로 나이트의 공격 범위를 관리하면, 좌표 값이 매우 큰 무한 체스판 환경에서도 간단하고 빠르게 정답을 판별할 수 있습니다.