Python 백준 8320번 - N-Queen, 백트래킹 알고리즘과 pruning(가지치기)

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

8-queen 애니메이션

나의 생각

처음 이 문제를 보았을 때, 당연스럽게 노트를 펴고 3*3 부터 5*5까지 경우를 그려보았다. 그려보면서 특징들을 살펴보았다.

1. 같은 행(row) 에는 반드시 하나의 퀸만 올 수 있다는 점.

2. 위의 조건 때문에 하나의 행씩 위에서 아래로 내려오면서 구할 수 있다는 점.

위 두가지 조건을 특징들을 발견하는 것은 그렇게 오래 걸리지 않았던 것 같다. 그렇지만 이것을 알고리즘으로 구현하는 것이 문제였다.. 우선 가장 위의 행부터 퀸을 하나 찍어본다. 그 후에 아래 행의 칸들 중에서 한 칸을 찍고 그 곳이 공격을 받지 않는 곳인지 판단하고 공격을 받지 않는 곳 이라면 다음 행으로 넘어간다.

이 N-qeen 문제는 대표적인 백트래킹 알고리즘이기 때문에 백트래킹 알고리즘의 정의와 문제 해결 방법에 대해서 정리해 보겠다.

 

백트래킹 알고리즘이란?

모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. (나무 위키 백트래킹 참조)

또한 백트래킹(backtracking)이란, 한정 조건을 가진 문제를 풀려는 전략이다. (ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89)

이 말이 너무 모호하기 때문에 조금 더 자세하게 알아보았다.

우선, 말그대로 백(back), 뒤로 추적(tracking)을 한다.라고 이해하였다. 아래 그림을 보면서 이해해보겠다.

https://www.quora.com/What-is-backtracking-Explain-in-detail-1

제리는 내가 좋아하는 캐릭터라서 가져와 보았다. 우선 제리가 치즈를 먹기위해서 갈 수 있는 경로는 1로 색칠되어 있는 곳들이다. 그러면 처음 제리가 있는 지점부터 많은 갈래길이 나오는데 갈래길을 가다 보면 가장 오른쪽 가장 위에 제리가 갈 수 도 있을 것이다. 이때가 중요한데, 이때 제리는 치즈가 없기(목표가 아니기) 때문에 뒤로 돌아서 이전 갈래길로 돌아가고 그 갈래길에서 가지 않았던 곳을 갈 것이다. 이것이 백트래킹의 기본 개념이다.

 

문제 해결 방법

백트래킹의 문제 해결 방법은 임의의 집합에서 기준에 따라 원소의 순서를 선택하면 된다. 이 개념을 n-queen에 적용해 보겠다.

1. 임의의 집합 - 퀸이 놓여질 수 있는 공간(board)

2. 기준 - 퀸이 공격이 받지 않도록

3. 원소의 순서 - 퀸을 놓을 수 있는 공간 (N) (n개인 이유는 위에 내 생각에서 반드시 퀸은 한 행에 하나만 놓을 수 있기 때문)

(문제 해결 방법은 '주니온TV 아무거나 연구소' 님의 강의에서 참고하였습니다.)

 

가지치기(pruning)

가지치기라는 작업을 내가 넣은 이유가 무엇일까? 바로 최적화 때문이다. pruning이라는 단어를 처음 들었을 때는, 전공 수업인 AI 입문 시간이었는데, 이때 'tic-tak-toe'게임의 알고리즘에 대해서 배울 때였다.

(사실 이때도 알게 모르게 백트래킹(backtracking) 개념을 배웠던 것인데, 과제에 치중하다 보니 알고리즘 개념에 대해서 깊게 공부를 못했던 것 같다..)

어쨌든, 이 가지치기가 왜 필요한지? 그리고 어떻게 하는지 알아보겠다.

필요성 - 백트래킹 알고리즘은 위의 정의처럼 일종의 brute force 알고리즘이기 때문에 효율이 굉장히 떨어질 것이다. 그래서 효율을 극대화하기 위해서 (시간 단축) 필요 없는 작업은 쳐내야 하는 것이 좋다.

pruning 과정 - 그림을 보면 이해가 빠를 것이다.

출처 : https://velog.io/@gyu716625/TIL20.05.13%EC%88%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-N-queens-%EB%B0%98%EB%B3%B5%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-String

위의 그림을 보면 N = 4, 4-queen인 경우이다. 이때 root 노드 에서 왼쪽으로 나온 자식 노드는 가장 위의 1행에서 가능한 첫 번째 경우이다. 이 경우는 당연히 valid (promising) 한상태이기 때문에 자식 노드로 내려간다. 자식 노드들은 그 아래 3개의 그림들이 있는데, 사실은 2행에 4가지 경우로 놓을 수 있기 때문에 4개가 그려져 있었을 것이다. 여기서 가장 왼쪽의 경우를 살펴보자.

핵심 : 조건이 유효하냐? 유효하지 않냐? (promising)

pruning 에 핵심은 트리에서 해당 노드에서 조건이 유효(맞지)하지 않다면 자식 노드로는 탐색하지 않는다!

즉, 다음 경우들은 볼필요 없이 다음 형제 노드로 이동하게 된다. n-queen 문제에서 조건은 무엇일까,

조건이 바로 위의 문제 해결 방법에서 기준(criteria)이다. 바로 현재 퀸을 놓은 곳이 공격을 받는 곳이라면, 조건이 맞지 않은 것이고 공격을 받지 않는 곳이라면 유효한 곳이기 때문에 다음 행으로 가서 경우를 찍어본다.

 

코드 1

import sys
 
result: int = 0
N = int(sys.stdin.readline().rstrip())
#N * N 짜리의 상태 공간을 생성한다.
board = [[0] * N for _ in range(N)]
 
#현재 놓는 노드가 유망한지(promising, valid) 판단하여 백트래킹할때 pruning을 적용한다.
#따라서 하위(자식) 노드로는 내려가지 않는다.
#이 함수가 백트래킹의 핵심인 promising 함수.
def isValid(row: int, column: int)-> bool:
    for i in range(row):
        for j in range(N):
            if abs(i-row) == abs(j-column) and board[i][j] == 1: return False #대각선 판별
            elif j == column and i != row and board[i][j] == 1: return False #수직 위치 
    return True
 
#깊이 우선탐색을 하면서 하위자식 즉, 다음 행을 하나씩 증가하면서 번호를 찍어준다.
def dfs(row: int):
    global result, board
    if row == N:
        result += 1
        return
    for column in range(N):
        board[row][column] = 1
        if isValid(row, column):
            dfs(row + 1)
            board[row][column] = 0
        else:
            board[row][column] = 0
 
for i in range(N):
    board[0][i] = 1
    dfs(1)
    board[0][i] = 0
print(result)

결과 1

역시 python 은 버거운건가,, 라는 생각이 들었다. pypy3도 안 되는 것으로 봐서는 최적화가 덜 된 듯하였다. 그래서 강의를 찾아보며 공부 후 조금 더 나은 코드를 구현하였다. 하지만 결과는 잘 나온다....

코드 2

import sys
 
N = int(sys.stdin.readline().rstrip())
col = [0] * (N + 1)
result: int = 0
def isValid(i, col):
    k = 1
    while k < i:
        if (col[i] == col[k] or i - k == abs(col[i] - col[k])):
            return False
        k += 1
    return True
 
def dfs(i, col):
#열 col이라는 List로 주어지게 됨.
# col list는 valid한 노드들이 찍혀있을 것임.
# 바로, index가 행, col[index]가 열
    global result
    n = len(col) - 1
 
    #i번째 위치와 col list 에 있는 값들을 확인하면서 promising 한지 체크한다.
    if isValid(i, col):
        if i == n : result += 1
        else:
            for j in range(1, n + 1):
                col[i+1] = j
                dfs(i+1, col)
dfs(0, col)
print(result)

결과 2

위 코드도 역시 python3에서는 시간 초과가 떴다.. 하지만 pypy3에서는 조금 긴 시간이지만 성공하긴 하였다.

 

느낀점 및 고찰

첫 번째 코드를 구현하는 데는 생각과 수정 총 5~6시간 정도 걸린 듯하다.. 백트래킹에 대한 개념도 잘 몰랐으며 배열(board)을 전부 만들어서 재귀와 pruning을 동시에 생각하다 보니 중간중간 꼬이고 해서 조금 오래 걸린 듯했다. 최적화를 하는데 더 이상의 생각이 들지 않아서 이론부터 다시 공부하고 다른 사람들의 방법을 참고하였다. 우선 조금의 위안이라고 느껴졌던 부분은 백트래킹과 가지치기를 깊게 공부하지 않고 그냥 머릿속 생각과 알고리즘 흐름만으로 얼추 맞추었다는 점이다. 그래도 개발자의 숙명은 최적화를 해야 하는 것이며, 하루정도 더 투자하여 성공은 하였다. 코드를 수정하면서 느낀 다른 부분은 꼭 2차원 배열인 공간을 만들지 않고 서라도 충분히 가능하다는 점이다. 이 방법은 동적 계획법(dp)에서도 그렇다고 하니 다음에 동적 계획법이나 백트래킹 문제가 나온다면 이런 생각도 해봐야겠다.