Programmers / N-Queen / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: N-Queen (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

문제 설명

---

나의 풀이

def check(x, y, n, board):
    # 위쪽 열 확인
    for i in range(y):
        if board[i][x] == 1:
            return False
    
    # 왼쪽 위 대각선 확인
    i, j = y - 1, x - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1
    
    # 오른쪽 위 대각선 확인
    i, j = y - 1, x + 1
    while i >= 0 and j < n:
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1
    
    return True
    

def solve(y, n, result, board):
    # 모든 퀸을 두었으면 가능한 경우이므로 +1 한 후에 종료
    if y == n:
        result[0] += 1
        return
    
    for i in range(n):
        if check(i, y, n, board):
            board[y][i] = 1
            solve(y + 1, n, result, board)
            board[y][i] = 0  # 백트래킹
        

def solution(n):
    answer = 0
    
    board = [[0] * n for _ in range(n)]  # 보드 생성
    
    result = [0]  # 결과 값
    
    solve(0, n, result, board)
    
    return result[0]

---

※ 알아야 할 것

https://www.acmicpc.net/problem/9663

백준의 N-Queen문제는 조건이 더 까다롭고 위 풀이로는 풀리지 않습니다! 위 문제를 푸신 분은 백준 N-Queen문제도 풀어보시는 것도 좋을 것 같습니다.