체스에 관한 것이라곤 퀸스갬빗밖에 없는 내가 체스 관련 알고리즘 문제를 풀게되었다.
당연히 내 힘으로 해결한 것은 아니고, 아무리 생각해도 이해가 잘 되지 않아 강의를 보았다 ㅠㅠ
나무위키에 쳐보니 이게 그렇게 컴퓨터공학도에게 유명한 문제라고??
난 아직 멀었나보다 ㅠㅠ

백트래킹

백트래킹이란 모든 경우의 수를 탐색하는 알고리즘이다.
완전 탐색과 유사하지만, 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 가지치기 (Pruning) 기법을 사용한다는 것이 다르다.
파이썬의 경우 재귀 효율이 나쁘지만 백트래킹의 경우 대부분 재귀 형식으로 풀면 깔끔하게 풀린다고 한다.

이번 N-Queen 문제는 백트래킹 알고리즘을 이용하면 효율적이라 한다!
아래에서 나오는 check() 함수가 가지치기를 해주는 역할의 함수이다.

알고리즘

N-Queen의 규칙을 간단하게 그림으로 나타내보자

아래의 그림은 Programmers에서 진행하는 스터디인 '파이썬 알고리즘 스터디'의 이선협 리더님의 ppt의 일부를 발췌하였다.

1. N이 4라고 가정할 경우, (1, 1)에 첫번째 퀸을 놓는다

2. 퀸은 가로로 무한정 이동할 수 있으므로 해당 행에는 더이상 퀸을 배치할 수 없다.

3. 퀸은 세로로도 무한정 이동할 수 있으므로 (2, 1)에도 배치할 수 없다.

4. 대각선 방향으로도 무한정 이동 가능하므로 (2, 2)도 역시 안된다.

5. 마침내 (2, 3)에는 새로운 퀸을 배치할 수 있다!

6. 같은 방식으로 계산해 본 결과 3번째 행은 어디에도 퀸을 놓을 수 없으므로 이후 탐색은 의미가 없다.

7. 해당방식으로 탐색해보면 위와 같이 서로 절대 만날 수 없는 경우를 찾을 수 있다.

Python 코드

해당 알고리즘을 파이썬 코드로 구현해보자!

# 세로, 대각선 방향으로 다른 퀸이 존재하는지 확인 (가지치기!)
def check(queen, y):
    for i in range(y):
        if queen[i] == queen[y] or y - i == abs(queen[y] - queen[i]):
            return False
    
    return True

# 가능한 방법의 수 리턴
def search(queen, y):
    count = 0
    n = len(queen)
    
    # y가 배열 범위를 초과하면 이미 배치가 끝난 것이므로 1 리턴
    if y == n:
        return 1
    
    # 퀸을 일단 배치한 후 check 함수로 배치할 수 있는 경우인지 확인
    for x in range(n):
        queen[y] = x
        
        if check(queen, y) is True:   
            count += search(queen, y + 1)
            
    return count
    
# 가로에 퀸을 1개만 놓을 수 있으므로 1차원 배열로 표현
# 행 : index, 열 : queen[index]
def solution(n):
    return search([0] * n, 0)

하노이의 탑 만큼은 아니지만 N-Queen 문제도 꽤 유명한 알고리즘 문제 유형인 것 같다.
아직 모르는 알고리즘이 많지만,
하나하나 도장깨기 느낌으로 꾸준히 공부해야 겠다!