Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 풀기: 무한 체스판에서 N개 나이트에 갇힌 킹의 체크메이트 판별하기

문제 개요

무한히 넓은 체스판이 하나 있다고 가정해 보겠습니다. 이 체스판은 일반 체스와 동일한 규칙을 따르며, 좌표 범위가 매우 넓어 -10⁹ ≤ x, y ≤ 10⁹로 주어집니다. 체스판 위에는 N개의 나이트(말)가 배치되어 있고, 킹의 좌표도 함께 주어집니다. 우리가 확인해야 할 것은 바로 이 킹이 체크메이트 상태인지, 즉 더 이상 유효한 수를 둘 수 없는지 여부입니다.

예를 들어 나이트의 위치가 [[2,1],[1,3],[3,6],[5,5],[6,1],[7,3]]이고 킹의 위치가 [4,3]이라고 해 보겠습니다.

이 경우 출력은 True가 됩니다. 킹이 이동할 수 있는 모든 인접 칸이 나이트의 공격 범위 안에 놓여 있어, 킹이 어디로도 피할 수 없기 때문입니다.

접근 방법

핵심 아이디어는 의외로 간단합니다. 체스판이 아무리 커도 우리가 살펴봐야 할 영역은 극히 일부이기 때문입니다.

  • 각 나이트가 공격할 수 있는 최대 8개의 좌표를 계산해 딕셔너리(해시 맵)에 미리 기록합니다.
  • 킹의 현재 위치를 기준으로 인접한 최대 8개 칸(자기 자신 제외)을 하나씩 검사합니다.
  • 공격받지 않은 칸이 하나라도 존재하면 킹은 그곳으로 이동할 수 있으므로 False를 반환하고, 모든 칸이 공격 범위 안이라면 체크메이트이므로 True를 반환합니다.

알고리즘 단계

  1. 비어 있는 딕셔너리 my_dict를 생성합니다.
  2. 각 나이트의 좌표 (x, y)에 대해, 그 나이트가 공격 가능한 8개 좌표 (x±2, y±1), (x±1, y±2)를 모두 my_dict에 기록합니다.
  3. 킹의 위치 (kx, ky)를 중심으로 -1부터 1까지의 오프셋을 이중 반복문으로 순회하며 인접 칸 (nx, ny)를 구합니다.
  4. (nx, ny)가 킹 자신의 위치가 아니면서 my_dict에 없다면, 즉 공격받지 않는 빈 칸이라면 즉시 False를 반환합니다.
  5. 반복문이 끝날 때까지 공격받지 않은 칸이 발견되지 않았다면 True를 반환합니다.

파이썬 구현

아래 예제 코드를 통해 더 쉽게 이해할 수 있습니다. 원본 로직에서 두 가지만 다듬었습니다. 첫째, 킹 자신의 위치만 건너뛰고 나머지 8방향을 모두 검사하도록 조건을 명확히 했고, 둘째, 딕셔너리의 get() 메서드를 사용해 존재하지 않는 키 조회 시 발생할 수 있는 KeyError를 방지했습니다.

def is_checkmate(a, n, king_pos):
    my_dict = {}
    for i in range(n):
        x = a[i][0]
        y = a[i][1]
        # 나이트 자신의 위치와 공격 가능한 8개 칸을 표시
        my_dict[(x, y)] = 1
        my_dict[(x - 2, y + 1)] = 1
        my_dict[(x - 2, y - 1)] = 1
        my_dict[(x + 1, y + 2)] = 1
        my_dict[(x + 1, y - 2)] = 1
        my_dict[(x - 1, y + 2)] = 1
        my_dict[(x + 2, y + 1)] = 1
        my_dict[(x + 2, y - 1)] = 1
        my_dict[(x - 1, y - 2)] = 1

    # 킹 주변 8방향 검사
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i == 0 and j == 0:
                continue  # 킹 자신의 위치는 제외
            nx = king_pos[0] + i
            ny = king_pos[1] + j
            if not my_dict.get((nx, ny)):
                return False  # 공격받지 않는 칸이 존재함
    return True  # 모든 이동 경로가 차단됨

a = [[2,1],[1,3],[3,6],[5,5],[6,1],[7,3]]
n = len(a)
pos = [4, 3]
print(is_checkmate(a, n, pos))

입력

[[2,1],[1,3],[3,6],[5,5],[6,1],[7,3]], 6, [4, 3]

출력

True

복잡도 분석

  • 시간 복잡도: O(N) — 나이트마다 상수 개수(8개)의 좌표만 기록하고, 킹 주변은 항상 최대 8칸만 검사하면 되므로 전체 작업량은 나이트 수에 비례합니다.
  • 공간 복잡도: O(N) — 딕셔너리에는 나이트당 최대 9개의 좌표만 저장되므로 메모리 사용량 역시 나이트 수에 비례합니다.

체스판 좌표가 -10⁹부터 10⁹까지 뻗어 있어도 실질적으로 확인해야 할 것은 나이트들의 공격 지점과 킹의 인접 칸뿐입니다. 이처럼 문제의 관심 영역을 좁혀 해시 맵으로 관리하면, 무한에 가까운 보드에서도 선형 시간 안에 체크메이트 여부를 손쉽게 판별할 수 있습니다.