[Algorithm] 프로그래머스 Lv.3 N-Queen (backtracking, python3)

문제링크

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

코딩테스트 연습 - N-Queen

 

문제설명

 

문제풀이

 

def promising(i, col):      # 대각선 방향 겹치는지 체크
    k = 1
    flag = True
    while k < i and flag:
        if col[i] == col[k] or (abs(col[i]-col[k]) == i-k):
            flag = False
        k += 1
    return flag

def nqueen(i,n,col):    # 같은 행, 같은 열인지
    global ans
    if promising(i, col):
        if i == n:
            ans += 1
        else:
            for j in range(1, n+1):
                col[i+1] = j
                nqueen(i+1, n, col)
    return ans

ans = 0
def solution(n):
    col = [0] * (n + 1)
    return nqueen(0,n,col)

 

def dfs(col,n,i):
    cnt = 0
    if n == i:
        return 1
    for j in range(n):
        col[i] = j
        for x in range(i):
            if col[x] == col[i]:
                break
            if abs(col[x] - col[i]) == (i-x):
                break
        else:
            cnt += dfs(col, n, i+1)
    return cnt

def solution(n):
    ans = dfs([0]*n, n, 0)
    return ans

 

 

다른 풀이

야매이긴 하지만, 백준 문제처럼 조건이 더 빡센 n-queen 문제에서는 유용한 풀이인 것 같다.

def solution(n):
    nQueen = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884, 314666222712, 2691008701644, 24233937684440, 227514171973736, 2207893435808352, 22317699616364044, 234907967154122528]
    return nQueen[n]