[백준] 9663 N-Queen 파이썬 풀이 (백트래킹)

백준

문제

• N*N 체스판에 퀸 N개를 놓는다
• 퀸의 좌우상하 대각선에 다른 퀸이 없어야한다.
• 그렇게 N개를 놓는 경우의 수를 출력하라

 

문제 풀이

<백트래킹>

맨 위에 줄 1번째 칸부터 확인한다

두번째 줄에 되는 칸이 있으면

세번째 줄로 내려간다

세번째 줄에 되는 칸이 없다

그럼 다시 두번째 줄로 올라간다

 

두번째 줄로 올라가서 다음칸을 확인한다

세번째 줄로 가서 되는 칸이 있는지 확인한다

네번째 줄로 가서 되는 칸이 있는지 확인한다

없다

그럼 1번째 줄 두번째 칸으로 올라간다

 

1번째 줄 두번째 칸을 확인한다

두번째 줄에서 되는 칸이 있는지 확인한다

세번째 줄에 되는 칸이 있는지 확인한다

네번쨰 칸에 되는 칸이 있는지 확인한다

있으면 횟수를 하나 올린다.

 

 

코드

 

def adjacent(x): # x와 i 가 같으면 행이 같은거 근데 for문을 보면 x와 i가 같을 수가 없다.
    for i in range(x): #인덱스가 행  row[n]값이 열
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i: # 열이 같거나 대각선이 같으면 false
            return False # 대각선이 같은경우는 두 좌표에서 행 - 행 = 열 - 열 이 같으면 두개는 같은 대각선상에 있다.
    return True
 
#한줄씩 재귀하며 dfs 실행
 
def dfs(x):
    global result
 
    if x == N:
        result += 1
    else:
        # 각 행에 퀸 놓기
        for i in range(N): # i 는 열번호 0부터 N 전까지 옮겨가면서 유망한곳 찾기
            row[x] = i
            if adjacent(x): # 행,열,대각선 체크함수 true이면 백트래킹 안하고 계속 진행
                dfs(x + 1)
 
# N = int(input())/
N = int(input())
row = [0] * N
result = 0
print(row)
dfs(0)
# print(row)
print(result)

 

---

row가 뜻하는 것은

몇번째 줄에 몇 번째 칸에 있냐는 뜻이다

이것은

row = [1, 3, 0, 2] 가 된다

첫번째 줄 1번 인덱스에 퀸이있다

두번째 줄 3번 인덱스에 퀸이 있다.

세번째 줄 0번 인덱스에 퀸이 있다

네번째 줄 2번 인덱스에 퀸이 있다.

 

x == N이라는 뜻은 네번째 줄까지 맞는게 있어서 다 돌았다는 뜻이므로

횟수를 하나 증가해도 된다는 뜻이다.