N-Queen ( 9663번 )

9663번: N-Queen

 

나의 풀이

import sys

def _check(now_raw):
    for idx in range(now_raw):
        if (visit[idx] == visit[now_raw]) or ((now_raw - idx) == abs(visit[idx] - visit[now_raw])):
            return False
    return True

def _dfs(raw):
    global answer
    if (raw == n):
        answer += 1
    else:
        for col in range(n):
            visit[raw] = col
            if _check(raw):
                _dfs(raw + 1)

n = int(sys.stdin.readline().rstrip())
visit = [-1] * n
answer = 0

_dfs(0)
print(answer)

 

시간 복잡도

def _check(now_raw):
    for idx in range(now_raw):
        if (visit[idx] == visit[now_raw]) or ((now_raw - idx) == abs(visit[idx] - visit[now_raw])):
            return False
    return True

def _dfs(raw) : 백트래킹 ( 팩토리얼 시간복잡도 )
    _check(now_raw) : 이전 행 탐색 ( 선형시간 복잡도 )
    
해당 알고리즘 시간 복잡도 : 팩토리얼 선형 시간 복잡도 ( O(n! × n) )