[Python] 백준 9663_ N-Queen
https://www.acmicpc.net/problem/9663
**다음 내용은 유튜브 '바킹독'님의 백트래킹 강의를 듣고 작성한 내용이다. (youtube.com/watch?v=Enz2csssTCs&t=1237s)
이 문제는 백트래킹을 이용하여 해결할 수 있는 문제이다.
체스에서 퀸은 일직선으로 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동가능하므로 먼저 열(앞/뒤), 상향 대각선, 하향 대각선 방향에 이미 말이 존재하는지 체크를 해준다.
check1 =[True]*n #열확인
check2 =[True]*(n*2-1) #대각선확인 (x+y)
check3 =[True]*(n*2-1) #대각선확인 (y-x)
-
check1 : 열확인
-
check2: 상향 대각선 확인
예를 들어, 인덱스 (2,2), (1,1), (0,2)는 한 대각선에 위치한다.
이때 (x,y)에서 x+y는 모두 같은 것을 확인할 수 있다.
- check: 하향 대각선 확인
예를 들어, 인덱스 (0,1),(1,2),(2,3)는 한 대각선에 위치한다.
이때 (x,y)에서 y-x는 모두 같은 것을 확인할 수 있다.
코드
import sys
input = sys.stdin.readline
n = int(input())
#퀸은 일직선으로 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동가능
check1 =[True]*n #열확인
check2 =[True]*(n*2-1) #대각선확인 (x+y)
check3 =[True]*(n*2-1) #대각선확인 (x-y)
cnt=0
def func(num):
global cnt
if num ==n: #퀸을 모두 체스판에 놓았으면 cnt+=1
cnt+=1
return
for i in range(n):
if check1[i] and check2[i+num] and check3[num-i+n-1]:
#모두 조건을 만족하면(check3: num-i+n-1인 이유는 계산한 값이 음수가 되는 것을 방지하기 위해서이다.)
check1[i]=False
check2[i+num]=False
check3[num-i+n-1]=False
func(num+1)
check1[i]=True
check2[i+num]=True
check3[num-i+n-1]=True
func(0)
print(cnt)
Author And Source
이 문제에 관하여([Python] 백준 9663_ N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soobin519/Python-백준-9663-N-Queen저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)