[Python] 26006번 K-Queen

 

 

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

26006번: K-Queen

---

 

22/12/01

 

 

그룹 연습 문제로 나왔던 문제를 풀었다. 실버 3치고는 개인적으로 어려웠던 편에 속해서, 실버 2로 충분히 올라가도 될 것 같다.

---

 

문제 접근 방식:

 

 

전형적인 구현 문제이지만, 구현을 잘 못한다면 어렵게 돌아갈 가능성이 존재한다.

 

먼저, 나는 흰색 킹이 8방향으로 움직일 수 있다는 점에 착안하여, BFS를 구현할 때처럼 dr, dc배열을 선언해주었다.

 

이후 흰색 킹이 현재 위치한 칸과 흰색 킹이 현재 갈 수 있는 칸들을 저장하는 move_li 배열을 dr, dc배열을 통해 구현해 주었다.

 

여기까지 작성해놓고, 체크메이트가 되는 상황, 체크가 되는 상황, 스테일메이트가 되는 상황과 그 이외의 상황을 곰곰이 생각해보았다.

 

 

먼저, 체크메이트 또는 체크가 되려면 현재 흰색 킹이 위치한 칸이 공격을 받는 위치여야 한다.

 

이후, 체크메이트가 되려면, 그 외의 흰색 킹이 갈 수 있는 모든 칸들이 공격을 받는 위치여야 한다.

 

 

흰색 킹이 위치한 칸이 공격을 받는 위치가 아니라면, 스테일메이트인지 아닌지를 판단할 수 있다.

 

만약 스테일메이트이려면 흰색 킹이 위치한 칸이 공격을 받지 않는 상황이면서, 동시에 흰색 킹이 갈 수 있는 모든 칸들이 공격을 받는 위치여야 한다.

 

 

나는 여기까지 생각해놓고, 이후 구현을 생각해보았다.

 

맨 처음 생각한 방법은 체스판 배열을 직접 선언하여, 체스판 배열에 퀸이 공격할 수 있는 칸들을 모두 색칠하는 방법이었다.

 

생각해보니 체스판 배열을 직접 선언하는 방법은 시간면에서나 메모리 면에서나 많은 손해를 볼뿐더러, 메모리 제한을 벗어난다는 사실을 알 수 있었다.

 

 

나는 N-Queen문제에서 아이디어를 얻어, 이 문제를 해결할 수 있다고 생각했다.

 

먼저, 흰색 킹이 움직일 수 없는 칸들, 다시 말해, 흰색 킹이 검은색 퀸에게 공격을 받는 칸들을 저장하는 immove_set을 선언해주었다.

 

이후 퀸의 좌표를 하나 입력받을 때마다 move_li의 원소들을 반복해서 판단해주는데, 만약 공격 범위에 있는 칸이라면, 그 칸을 immove_set에 넣도록 해주었다.

 

공격을 받는지 받지 않는지에 대한 여부는 다음과 같이 판단했다.

 

같은 열이나 같은 행에 있는지에 대한 판단은 쉽다. 중요한 것은 같은 대각선에 있는지에 대한 여부인데, 이는 행과 열의 간격의 절댓값이 서로 같아야 되므로, 이를 통해 판단하였다.

 

퀸의 개수 $K$가 최대 $100,000$까지이고, move_li의 원소가 최대 9개까지 있을 수 있으므로, 최대 $900,000$번 반복하여 연산을 진행한다.

 

시간 복잡도 $O(K)$로 문제를 해결할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 26006번 K-Queen
# 구현
import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
R, C = map(int, input().rstrip().split())

dr = [-1,-1,-1,0,0,1,1,1]
dc = [-1,0,1,-1,1,-1,0,1]
move_li = [(R, C)] + [(R+dr[i], C+dc[i]) for i in range(8) if 1<=R+dr[i]<=N and 1<=C+dc[i]<=N]
immove_set = set()

for i in range(K):
    R_i, C_i = map(int, input().rstrip().split())
    for mR, mC in move_li:
        if abs(mR-R_i) == abs(mC-C_i) or mR == R_i or mC == C_i:
            immove_set.add((mR, mC))

if (R,C) in immove_set:
    if len(move_li) == len(immove_set):
        print('CHECKMATE')
    else:
        print('CHECK')
else:
    if len(immove_set) == len(move_li)-1:
        print('STALEMATE')
    else:
        print('NONE')