[SWEA|파이썬] 2806. N-Queen (D3)

문제

https://tinyurl.com/2zrd5mef

SW Expert Academy

 

 

🐍파이썬

T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    board = [0] * n
    answer = 0

    def dfs(x):
        global answer
        if x == n:  #n행의 depth까지 들어갔다면
            answer += 1     #퀸 놓는 경우의 수+1
            return
        for i in range(n):  #n행 반복
            board[x] = i    #x행, i열에 퀸 놓기
            for j in range(x):
            	#해당 위치에 퀸을 놓을 수 있는지 없는지 확인
                #동일한 열에 있거나 or 대각선상에 있을 때 퀸 놓기 불가
                if board[x] == board[j] or abs(board[x]-board[j]) == abs(x-j):
                    break
            #break문 실행이 되지 않았을 때 -> 퀸을 놓을 수 있다.
            else:
                dfs(x+1)    #다음 재귀 실행해서 새로운 퀸 놓기
    dfs(0)
    print("#{} {}".format(test_case, answer))

 

N-Queen은 대표적인 백트래킹 문제이다.

아직 이해가지 않는 부분은 더 공부하고 반복해서 익히도록 하자.

 

참고한 블로그

https://seongonion.tistory.com/103

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

👆 자세한 코드 설명을 확인할 수 있다.

 

https://jehwanyoo.net/2022/01/26/n-queen-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9/

N-Queen 문제 (백트래킹)