[알고리즘 문제풀이] N-Queen

문제 제목 : N-Queen

문제 난이도 : 중

문제 유형 : 백트래킹

https://www.acmicpc.net/problem/9663
시간 제한 : 10초
메모리 제한 : 128MB

문제풀이 아이디어

< 소스코드 >

n = int(input())
row = [0] * n
result = 0

# x행에 놓은 Queen에 대해 검증
def check(x):
    for i in range(x):
        # 위, 대각선 확인
        if row[x] == row[i]:
            return False
        if abs(row[x] - row[i]) == x - i:
            return False
    return True

# x행에 대한 처리
def dfs(x):
    global result
    if x == n:
        result += 1
    else:
        for i in range(n):
            row[x] = i
            if check(x):
                dfs(x + 1)

dfs(0)
print(result)