백준 9663) N-Queen [ Python, 백트래킹 ]

 

---

분류 : DFS, 백트래킹

문제는 굉장히 담백한데, 백트래킹을 잘 이해하지 못하면 풀기 힘들다. 

---

keypoint : DFS, 백트래킹

---

code

import sys
input = sys.stdin.readline
 
n = int(input())
	
visited = [-1] * n
cnt = 0
 
def check(now_row):
    for row in range(now_row):
        if visited[now_row] == visited[row] or now_row - row == abs(visited[now_row] - visited[row]):
            return False
    return True
 
def dfs(row):
    global cnt
    
    if row == n: 
        cnt += 1
 
    else:
        for col in range(n):
            visited[row] = col
            if check(row): 
                dfs(row + 1) 
                
dfs(0)
print(cnt)

---

중요한 내용 

체스판의 모든 경우의 수를 구현하기 위해 2차원 배열을 사용하지 않아도 된다는 것이 인상적인 풀이 방식이었다.

1차원 배열을 initialize 해놓고 배열 각 요소의 값이 열이 되고 인덱스가 행의 값이 되는 풀이 방식으로 2차원 배열을 사용하지 않아도 되는 문제 풀이 방식인데 위 코드를 하나하나 찢어서 해석해보겠다.

 

 

같은 열에 퀸이 있는지 확인하는 코드이다.

def check(now_row):
    for row in range(now_row):
        if visited[now_row] == visited[row] or now_row - row == abs(visited[now_row] - visited[row]):
            return False
    return True

 

visited[now_row] == visited[row] 는 0부터 now_row-1 까지의 행을 검사하면서 같은 열 { 배열의 값이 '열' 값이다. }에 퀸이 있는지 검사하는 코드이다. 

 

now_row - row == abs(visited[now_row] - visited[row]) 는 대각선에 위치한 퀸이 있는지 검사하는 코드이다. 

now_row - row 는 현재 위치에서 row 까지의 거리를 의미한다. 대각선에 위치한다면 '열' 과 같은 값만큼 떨어져 있을테니 now_row - ro == abs(visited[now_row] - visited[row]) 가  True 라면 대각선에 퀸이 존재하는 것이므로 False 를 반환하게 된다.

 

 

def dfs(row):
    global cnt
    
    if row == n: 
        cnt += 1
 
    else:
        for col in range(n):
            visited[row] = col
            if check(row): 
                dfs(row + 1)

 

체스판에서 row 가 n 까지 잘 움직여 퀸을 놓았다면 cnt를 1추가 한다. 

 

n 까지 커지기 전, 재귀적으로 퀸을 놓았던 하나의 칸마다 다음 단계의 가능성을 체크하게 된다.