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')
'PS > 연습' 카테고리의 다른 글
[PS] [Baekjoon] 2866. 문자열 자르기 (0) | 2025.01.12 |
---|---|
[PS] [Baekjoon] 15783. 세진 바이러스 (1) | 2024.12.27 |
[PS] [Baekjoon] 9464. 직사각형 집합 (0) | 2024.12.20 |
[PS] [Baekjoon] 20541. 앨범 정리 (0) | 2024.12.19 |
[PS] [Baekjoon] 15791. 세진이의 미팅 (1) | 2024.12.03 |