[프로그래머스] Level 2 - N-Queen (Python)

 

 

 

 

 

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

코딩테스트 연습 - N-Queen

 

 

 

 

 

✅ Solution

• 첫 번째 열부터 차례대로 퀸을 추가한다.
• 퀸을 추가하고, 이전에 놓였던 퀸들과 행이 같지 않아야 하며 대각선에 위치하지 않아야 하는 조건을 체크한다.
  • 열마다 하나씩 퀸을 추가할 것이므로 열이 같은 경우는 존재하지 않으므로 열에 대한 고려는 해주지 않아도 된다. (항상 하나의 열에 퀸 하나만 존재)
•  new_queen_col == prev_queen_col 또는 abs(new_queen_col - prev_queen_col) == new_queen_row - prev_queen_row 일 경우 해당 위치에 퀸을 추가할 수 없으므로 종료시킨다.
  • 대각선에 위치한다는 것은 기울기가 같다는 것을 의미한다. 따라서 기울기로 비교해주면 된다.

 

 

 

 

✅ Code

def nqueen(queens, next_queen, n):
    global answer

    if next_queen in queens:  # 같은 행에 있는지 체크
        return

    for row, col in enumerate(queens):
        next_queen_row = len(queens)
        if abs(next_queen - col) == next_queen_row - row:  # 대각선에 있는지 체크
            return

    queens.append(next_queen)

    if len(queens) == n:
        answer += 1
        return

    for next_queen in range(n):
        nqueen(queens[:], next_queen, n)


def solution(n):
    global answer
    answer = 0

    for next_queen in range(n):
        queens = []
        nqueen(queens, next_queen, n)

    return answer