N-Queen 문제 (백트래킹)

문제

https://programmers.co.kr/learn/courses/30/lessons/12952

알고리즘 유도

체스판은 2차원 배열로 되어있다.

퀸들끼리 서로 간섭하지 않고 총 N개의 말을 체스판에 놓아야한다.

1줄부터 N줄까지 차례대로 퀸을 규칙대로 놓으면 정답을 구할 수 있다.

백트래킹

DFS를 진행하면서 가려고하는 노드의 유망성을 판단하여 전진할지 후퇴할지 결정하는 알고리즘이다.

1줄부터 퀸을 계속 놓는다. 그리고 더이상 퀸을 놓을 수 없으면 후퇴한다. (유망하지 않기 때문이다.)

만약 N번째 줄까지 퀸을 문제없이 놓았다면 정답으로 취급하고 count에 1을 더한다.

가지치기(pruning) 조건

1. 같은 열(column)에 위치한다.
2. 대각선에 위치한다.

1번 조건은 간단하지만 2번 조건은 좀 생각해 봐야 한다.

💡 한 줄씩 진행하므로 같은 행에 놓는 경우는 존재하지 않는다.

대각선 판단

퀸들이 서로 대각선 위치에 존재할 경우,

직각 이등변 삼각형을 그릴 수 있다.

즉, 밑변과 높이의 길이가 같다는 뜻이다.

코드

def nqueen(row, pos, n):
    count = 0
    if row == n:  # 정답을 찾았을 경우
        return 1
    else:
        for col in range(n):  # 첫번째 열부터 마지막 열까지 탐색
            pos[row] = col
            for i in range(row):  # 유망성 판단
                if pos[i] == pos[row]:  # 같은 열
                    break
                elif abs(i - row) == abs(pos[i] - pos[row]):  # 대각선
                    break
            else:  # 유망할 경우 다음 행으로 진행
                count += nqueen(row + 1, pos, n)
    return count

def solution(n):
    return nqueen(0, [0] * n, n)

일반적으로 알려진 수도 코드(pseudo code)로 푸는 방법이다.

N-Queen 백트래킹 최적화

def nqueen(row, pos, visited, n):
    count = 0
    if row == n:  # 정답을 찾았을 경우
        return 1
    else:
        for col in range(n):  # 첫번째 열부터 마지막 열까지 탐색
            if visited[col]:  # 이미 같은 열에 체스말이 놓여있으면 탐색하지 않음
                continue
            pos[row] = col
            for i in range(row):  # 유망성 판단
                if abs(i - row) == abs(pos[i] - pos[row]):  # 대각선
                    break
            else:  # 유망할 경우 다음 행으로 진행
                visited[col] = True
                count += nqueen(row + 1, pos, visited, n)
                visited[col] = False
        return count

def solution(n):
    return nqueen(0, [0] * n, [False] * n, n)

같은 열에 존재하는 경우 $O(1)$만에 유망성을 판단하도록 수정했다.

반복문을 도는 횟수가 크게 감소했다.

비고

백준에서 통과하려면 pypy3를 사용해야한다. (시간 초과 문제)

백트래킹 문제는 파이썬이 굉장히 불리하다.