[프로그래머스] N-Queen / Python

문제주소 :programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

---

<문제 설명>

문제 설명

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

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

 

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

제한사항

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

---

입출력 예

n                                                                        result

4

2

 

<풀이법>

▒ 한줄 개념: 백트래킹 알고리즘 ▒ 

백트래킹 알고리즘의 가장 대표적인 문제입니다.

백트래킹 알고리즘은 조건이 걸려있는 DFS로서 어떤 제한이 있는 경로탐색 문제에 주로 사용됩니다.

자세한 풀이는 이전에 백준에서 풀었던 N-Queen문제 게시글에 적어두었습니다.

2021/01/11 - [Baekjoon] - [백준9663] N-Queen / Java

 

<코드(Python)>

def solution(n):
    answer = 0
    for i in range(n):
        answer += search(n, [i])

    return answer


def search(n, board):

    if len(board) == n:
        return 1
    count = 0
    for i in range(n):
        right = True
        for j in range(len(board)):
            if board[j] == i:
                right = False
                break
            if abs(board[j] - i) == abs(j - len(board)):
                right = False
                break
        if right:
            count += search(n, board.copy()+[i])

    return count

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest