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

문제 정보

제목 : N-Queen

난이도 : Lv.2

사용 언어 : Python

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

문제 설명

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

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

 

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

 

제한 사항

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

입출력 예

n	result
4	2

 

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

---

나의 풀이

DFS를 이용했습니다. 열을 기준으로 row에 대해 검사하여  i번째 행의 컬럼값과, row행의 컬럼값이 같다면 같은 행에 퀸이 있는 것이므로 break합니다. 만약 i번째 행의 컬럼값과 row번째 행의 컬럼 값을 빼서 절대값을 취한 값이 row - i를 만족한다면 이는 대각선 상에 있는 것이므로 break합니다. 이 과정 중 if문에서 break된 것이 없고 마지막까지 도착한다면 count에 1을 더하고 반환합니다.

 

코드

def solution(n):
    answer = dfsQueen([0]*n,0,n)
    return answer

def dfsQueen(board,row,n):
    count = 0
    if n == row:
        return 1
    for col in range(n) :
        board[row] = col
        for i in range(row):
            if board[i] == board[row]:
                break
            if abs(board[i]-board[row]) == row - i:
                break
        else :
            count += dfsQueen(board,row+1,n)
    return count