⌨️ BOJ 9663: N-Queen
date
‣
slug
boj-9663
status
Published
tags
Algorithm
BOJ
summary
N x N 체스판에서 퀸 N개를 공격할 수 없게 놓는 경우의 수
type
Post
문제
- N-Quuen 문제
- N x N 체스판에서 퀸 N개를 공격할 수 없게 놓는 경우의 수
설명
- 백트래킹을 이용하면 풀리는 문제
- 총 3개의 리스트를 활용해서 놓을 수 있는지 체크했다.
- isUsed: 세로
- isUsed2: 우하향 대각선(x-y가 같은 경우). 단, 가장 낮은 값이 -N+1 이므로 배열에서 활용하기 위해 x-y+N-1을 인덱스로 활용한다.
- isUsed3: 우상향 대각선(x+y가 같은 경우)
세로를 체크하는 방법은 기존의 백트래킹과 똑같지만, 대각선 체크의 경우 떠올리지 못했다.
만약 모두 체크한다면 시간 복잡도가 O(n!)이지만, 아래와 같이 가지치기를 하면 이보다는 빨리 수행할 수 있다.