[PS] [Baekjoon] 26006. K-Queen

https://www.acmicpc.net/problem/26006

 

언어 : 파이썬 (Python3)

시작 : 2024.12.21 09:20

종료 : 2024.12.21 09:35

티어 : Silver II

비고 : 2022 홍익대학교 프로그래밍 경진대회 C번

 

태그 :

구현, 많은 조건 분기

문제 해석

 

N-Queen의 패러디 문제.

 

체스판에서, 퀸이 10만개 이하로 배치되어있을 때 킹의 현재 상태를 출력하는 문제다.

현재 위치가 퀸의 공격범위 일 때 "공격받고 있다"고 칭한다.

킹은 8방향으로 1칸 움직여 공격을 회피할 수 있다.

 

CHECK : 킹이 공격받고 있고, 이를 회피할 수 있을 때

CHECKMATE : 킹이 공격받고 있고, 이를 회피할 수 없을 때

STALEMATE : 킹이 공격받고 있지 않고, 어느 곳으로든 움직이면 공격받을 때

NONE : 위 경우 모두 아닐때

 

유의할 점은 2가지.

1) 체스 판의 크기는 $10^9$까지 커질 수 있으므로 배열을 만들어 푸는 방법은 통하지 않는다.

2) 입력은 킹이 퀸을 잡을 수 있게 주어지지 않는다. 즉, 킹 주변 1칸에 퀸은 존재하지 않는다.

풀이

 

퀸의 이동 경로를 살펴보면,

 

1) ←→. 해당 열($x$)을 공격할 수 있다.

2) ↑ ↓. 해당 행($y$)을 공격할 수 있다.

3) ↖↘.  $x-y$가 퀸이 있는 칸과 일치하는 모든 칸을 공격할 수 있다.

4) ↙↗. $x+y$가 퀸이 있는 칸과 일치하는 모든 칸을 공격할 수 있다.

 

각 경우에 대해 4개의 set를 만들고 해당하는 숫자를 더해주면 된다.

얘를 들어 $(x, y)$가 $(2, 3)$ 인 퀸은,

1번 set에 2를,

2번 set에 3을,

3번 set에 2-3을,

4번 set에 2+3을 add한다.

 

 

그 후 격자 바깥을 제외하고 각 set와 비교해가며 킹이 이동 가능한 칸을 구하고,

킹이 현재 공격받고 있는지 여부를 체크 한 뒤 경우에 맞게 출력하면 된다.

코드

 

풀이 1) 성공, 246ms

import sys
input = sys.stdin.readline

def can_move(x, y):
    if 1 <= x <= N and 1 <= y <= N:
        if kx in x_set:
            return False
        elif ky in y_set:
            return False
        elif kx + ky in sum_set:
            return False
        elif kx - ky in sub_set:
            return False
        else:
            return True
    return False

N, K = map(int, input().split())
R, C = map(int, input().split())
arr = [tuple(map(int, input().split())) for _ in range(K)]

sum_set = set()
sub_set = set()
y_set = set()
x_set = set()

for y, x in arr:
    x_set.add(x)
    y_set.add(y)
    sum_set.add(x+y)
    sub_set.add(x-y)

king_move = set()
king_attacked = False
for dy in range(3):
    for dx in range(3):

        kx = C + dx - 1
        ky = R + dy - 1

        if dx == dy == 1:
            king_attacked = not can_move(kx, ky)
            continue

        elif can_move(kx, ky):
            king_move.add((kx, ky))

if king_attacked:
    print('CHECK' if king_move else 'CHECKMATE')
else:
    print('NONE' if king_move else 'STALEMATE')