[v.백트래킹-N-Queen-9663]BAEKJOON_Python

220126 작성

<본 블로그는 BAEKJOON 을 참고해서 저만의 풀이를 작성하였습니다>

 

 

 

9663

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램

 

 

내 풀이

def backTracking(rowPos) :
    global answer

    # 퀸 모드 배치하면 끝!
    if rowPos == n :
        answer += 1
        return
    
    for col in range(n) :
        flag = True
        # 이전 행들
        for row in range(rowPos) :
            # 같은 열에 있거나, 대각선에 퀸이 이미 존재하면 가지치기
            if queenLocate[row] == col or rowPos -row == abs(col-queenLocate[row]) :
                flag = False
                break

        if flag :
            queenLocate[rowPos] = col
            backTracking(rowPos + 1)

n = int(input())
answer = 0

# 각 row 마다 queen 위치 인덱스 저장리스트
queenLocate = [0] * n
backTracking(0)
print(answer)

1. 각 행마다 Queen은 하나만 존재해야 하므로, 맨 위 행부터 내려오기

2. 각 행에서 이전 행들을 관찰하면서 같은 열이나 대각선에 퀸이 있다면 가지치기

3. 맨 밑의 행까지 퀸을 위치할 수 있다면 경우의 수를 하나 증가

 

 

 

 

 

 

8
92

 

 

 

 

 

참고한 블로그 입니다! 설명 감사합니다1 bbb

체스,, 원리 모르면 못 풀 듯요 ㅡ,ㅡ,ㅜㅡㅜ

아직도 이해가 안가느으ㅡ,,

https://studyandwrite.tistory.com/393

 

[백준(파이썬/Python)] 9663_N-Queen - 백트랙킹