[BOJ/백준] 9633 N-queen

def nqueen(x):
    global cnt
    for i in range(x+1):
        if x != i:
            if (visited[i] == visited[x]) or (abs(visited[i]-visited[x]) == abs(i-x)):
                return
    if x == N-1:
        cnt += 1
        return
    for i in range(N):
        visited[x+1] = i
        nqueen(x+1)



N = int(input())
cnt = 0
visited = [-1] * N
for i in range(N):
    visited[0] = i
    nqueen(0)
print(cnt)

백트래킹을 이용한 유명한 문제 중 하나이다.

 

적절하게 백트래킹을 하지 않고, 전체탐색을 할시 순열이라, 시간초과가 날 수 밖에 없다.

 

이 문제는 N과 같은 크기의 visited 1차원 리스트를 만들어줬다.

 

각 인덱스는 행을 나타내고, 그 안의 값은 열을 나타낸다고 가정을 하자.

 

그래서 첫번째 행에 0~N-1까지 넣어주고 그 뒤에 nqueen이라는 함수를 실행시켰다.

 

이 안에서도, 각 인덱스를 넣어주면서 재귀를 진행하는데, 만약에 값이 같은게 있거나, 인덱스의 차와 값의 차이가 동일하시 이것은 대각성분에 존재하는것이므로 종료를 해준다.

 

위 조건에 걸리지 않고 N-1까지 오면, 모든 곳을 탐색한 것이므로 함수를 종료해주면서 cnt를 1 늘려주면 된다.