[프로그래머스] 'N-Queen' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [다른 사람의 풀이]

---

 

문제 설명

 

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

흐림주의

 

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

 

 

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

 

입출력 예

n	result
4	2

알고리즘 분석

 

• 다른 사람의 풀이

def recur(n, board):
    global count

    if len(board) == n:
        count += 1
        return

    candi = list(range(n))

    for i in range(len(board)):
        if board[i] in candi:
            candi.remove(board[i])
        dis = len(board) - i
        if board[i]+dis in candi:
            candi.remove(board[i]+dis)
        if board[i]-dis in candi:
            candi.remove(board[i]-dis)
    if candi:
        for i in candi:
            recur(n, board+[i])
    return 0

count = 0
def solution(n):
    for i in range(n):
        recur(n, [i])
    return 0

 

이 문제는 다른 블로그를 참고했습니다. 

 

 

[BOJ] 👸 N-Queens / 파이썬

 

 

 

코딩테스트 연습 - N-Queen