[백준] 9663번 N-Queen(파이썬)

문제

9663번: N-Queen

코드

def dfs(x):
    global Queen
    # 맨 끝 행까지 온 경우 모두 놓을 수 있는 자리이니 += 1
    if x == n:
        Queen += 1
        return
    
    # 행 기준으로 돈다(행이 겹치지 않도록)
    for y in range(n):
        # 열과 좌우 대각선에 겹치는 부분이 없는지 본다
        if not visited_1[y] and not visited_2[x+y] and not visited_3[x-y]:
            #  돌았다면 체크 후 다음 행으로 넘어간다
            visited_1[y] = visited_2[x+y] = visited_3[x-y] = 1
            dfs(x+1)
            # 재귀가 풀릴때 체크를 풀어준다
            visited_1[y] = visited_2[x+y] = visited_3[x-y] = 0
    

n = int(input())

# 같은 열에 있는 지 체크하는 visited
visited_1 = [0] * n
# 우측에서 내려오는 대각선에 있는지 체크하는 visited
# x+y가 같은 값을 나타내기때문에 최대 n+n을 체크 할수 있게 (2 * n)
visited_2 = [0] * (2 * n)
# 좌측에서 내려오는 대각선이 있는지 체크하는 visited
# x-y가 같은 값을 나타내기때문에 최대 n+n을 체크 할수 있게 (2 * n)
visited_3 = [0] * (2 * n)
Queen = 0
dfs(0)
print(Queen)

해설

처음 접하는 백트레킹의 n-queen문제 유튜브에서 설명강의를 보고 풀이하였다.

자세한 해설은 코드 주석을 참고하자.

n-queen문제는 특정 자리에 queen을 놓으면 행/열/대각선 부분에 놓지못하도록 하는 문제이다. 그래서 행을 기준으로 하나씩 돌며 열과 대각선자리가 비어있다면 하나씩 놓아주면서 dfs방식으로 체크해주고 더이상 갈 수 없으면 재귀를 풀어주며 체크를 풀어주며 다른 길을 찾아보는 방식으로 풀이하는 문제였다.