[백준] 9663 N-Queen Python 풀이 와 백트래킹, 그리고 DFS의 비효율적인 사용

백트래킹 문제로 되게 유명하다면서/!??! 그래서 풀어봤다 백트래킹 유형중에 백준에서 푼사람이 가장 많은 문제이기도 하다 

백트래킹이란 ?

해를 찾는 도중에 해당 노드가 해가 아니라서 막히면 되돌아가서 다시 해를 찾아가는 기법이다.

 

첫번째 풀이는 시간초과가 났다 

dfs로 퀸을 배치하고, 배치한다음에 시뮬레이션 돌려서 퀸을 공격할 수 있는지 없는지 여부를 true , false 로 반환해서

true 값을 세려고 했다 시간 초과 판정이 떴다. 퀸을 배치하는 과정에서 조금 더 개선해볼 수 있지 않을까 ??? 

 

# 9663 N-Queen
n = int(input())

graph = [[0]*n for _ in range(n)]

dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]

def simulate(x, y): # x, y는 queen's position
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if graph[nx][ny] == 0:
                graph[nx][ny] = 1
                simulate(nx, ny)
            else:
                return False
    return True
result = 0
# 여기서 설치하기
def dfs(count):
    global result
    if count == n: # 퀸의 개수가 n개 일때

        for i in range(n):
            for j in range(n):
                if graph[i][j] != 0:
                    if simulate(i, j) == True:
                        result += 1
                        return
                    else:
                        return
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 0:
                graph[i][j] = 1
                count += 1
                dfs(count)
                graph[i][j] = 0
                count -= 1


dfs(0)
print(result)

 

+ 조금 덧붙이자면, 내가 쓴 첫 풀이는 DFS의 단점을 제대로 보여주는 예시이다 😅

DFS (깊이 우선 탐색)은 가능한 모든 후보를 탐색한다. 따라서 조건에 따라 불필요할 것 같아 보이는 경로를 사전에 차단하는 절차가 없으므로 , N-Queen 같은 경우의 수를 따지는 문제에서 비효율적으로 처리하게 된다. 

반면에 백트래킹은 모든 가능한 경우의 수들 중에서 조건을 만족하는 경우만 살펴볼 수 있다. 조건을 만족하지 않으면, 탐색을 중지 시킨 뒤 Back 하여 탐색 이전 단계로 돌아가서 다른 경우를 탐색하도록 구현한다.

 

< 더 효율적인 풀이 >

queen을 배치할 때부터 놓을 수 있는 자리인지 확인해주고, queen의 개수가 8개가 되면 true 를 반환하기 ?

효율적으로 구현하기 위해서는 queen 이 이동가능한 상하좌우 대각선을 한칸씩 이동해가면서 체크하는 것 보다,

대각선 \, 대각선 /, 세로 | 를 나타내는 각각 세개의 배열을 만들어서 체크하는 방법이 있다 !!! 

1. [x - y + n - 1] 대각선 \

현재 n=5이고, 0 ~8 총 9개의 경우가 있다. 2*n-1 개의 경우를 확인해봐야 한다.

2. [x+y] 대각선 /

현재 n=5이고, 0 ~8 총 9개의 경우가 있다. 2*n-1 개의 경우를 확인해봐야 한다.

3. [y] 세로 방향 (상하좌우의 경우 모두 확인 가능함)

n = 5, 경우의 수 또한 5가지이다. 

< 코드 설명 >

dfs함수의 인자 i로 현재 queen을 설치한 개수를 count한다. 

배열 a 는 세로 | , b는 대각선 /, c는 대각선 \ 방향의 상태를 나타낸다. 

세로방향 , 대각선 /, 대각선 \ 가 모두 false 이면 현재 queen 이 없는 상태이므로 새로운 queen을 배치할 수 있다 !!

새로운 queen 하나를 배치한 후 solve(i+1) 를 재귀호출한다 

그리고 다시 배치한 queen을 제거하여 백Back! 트래킹한다 

n = int(input())
result = 0
a = [False]*n
b = [False]*(2*n-1) # 대각선에 올 수 있는 가짓수
c = [False]*(2*n-1)

def dfs(i):
    global result
    if i == n:
        result += 1
        return
    for j in range(n):
        if not (a[j] or b[i+j] or c[i-j+n-1]): # 세 위치 모두 False이면
            a[j] = b[i+j] = c[i-j+n-1] = True # 세로 방향 확인, / 대각선, \ 대각선에 퀸 추가
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False
       

dfs(0)
print(result)