[Baekjoon] Baekjoon 9663 N-Queen 문제 풀이 및 공부
Baekjoon 을 통해 알고리즘 공부를 하는 중에 백트래킹 문제들을 풀다가 고난이도 문제를 만나게 되었습니다. 혼자서 풀다가 도저히 풀지 못하겠어서 해당 문제 풀이를 찾았지만 이해가 가지 않았습니다. 하지만 현재는 문제 풀이 방법에 대해서 이해를 했고, 이 과정을 포스트로 작성하여 스스로 공부하는 차원에서 정리하고자 하였습니다.
1. 문제 소개
이 문제는 Baekjoon 의 9663번 문제로 문제의 내용은 다음과 같습니다
- 시간 제한 : 10초
- 메모리 제한 : 128 MB
N-Queen 문제는 크기가 N x N 인 체스판 위에 퀸 N 개를 서로 공격할 수 없게 놓는 문제이다. N 이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N 이 주어진다. ($1 \le N \lt 15$)
출력
첫째 줄에 퀸 N 개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력1
8
예제 출력1
92
2. 문제 풀이
2.1 처음 접근 방식
- 체스의 퀸은 상하좌우와 대각선을 칸 수에 상관없이 모두 이동이 가능한 기물로써 퀸을 보고 행과 열 그리고 대각선에 다른 퀸이 놓여 있으면 안되겠다는 생각을 함
- 해당 문제가 백트래킹 문제라 다른 백트래킹 문제들과 같이 재귀함수와 함께 백트래킹을 하도록 해야 함을 알았지만 어떻게 구현을 해야할지 감을 잡지 못함
- 그렇다고 N x N 체스판과 같은 이차원 배열(리스트)를 만들어 반복문을 돌려가며 현재 놓여져 있는 퀸의 위치에 따라 모든 체스판을 체크하기에는 시간 제한으로 인해 시간 초과가 발생할 것 같다는 생각을 함
2.2 N-Queens 문제 검색
단순히 문제를 풀기 위한 것이 아니라 공부를 하기 위해 N-Queens 문제를 검색해봤습니다. 그러다 N-Queens 문제에 대한 풀이와 구현에 대한 유튜브 영상을 찾게 되었습니다. https://www.youtube.com/watch?v=z4wKvYdd6wM&feature=youtu.be
해당 영상을 통해 코드 구현을 다음과 같이 진행하고자 했습니다. 설명은 아래와 같은 4x4 체스판을 이용해 설명을 진행하도록 하겠습니다.
2.2.1 문제 풀이 과정
-
체스판에 퀸여 놓여져 있을 때 퀸을 놓지 못하는 조건 구현
- 퀸이 놓인 곳의 행과 같은 열에는 다른 퀸을 놓지 못함
- 대각선 조건1 퀸이 놓여 있는 곳의 행과 열을 뺀 값이 같은 곳들은 퀸이 놓일 수 없고 대각선은 오른쪽 아래(↘) 와 왼쪽 위(↖) 대각선임
- 대각선 조건2 퀸이 놓여 있는 곳의 행과 열을 더한 값이 같은 곳들은 퀸이 놓일 수 없고 대각선은 왼쪽 아래(↙) 와 오른쪽 위(↗) 대각선임
-
1번의 조건들과 함께 백트래킹을 이용해 구현
cnt = 0
def n_queens (i, col):
n = len(col)-1
# 현재 행의 위치에 퀸을 놓았을 때 퀸을 놓을 수 있다면
if (promising(i, col)):
# 현재 행이 마지막 행이라면
if (i == n):
global cnt
cnt+=1
return
else: # 현재 행이 마지막 행이 아니라면 1~n 까지 열 체크
for j in range(1, n+1):
col[i+1] = j
n_queens(i+1, col)
# i 행에 대해서 퀸을 놓을 수 있는지 못 놓는지 판별 하는 함수
def promising (i, col):
k = 1
flag = True
"""
col 리스트에서 index 는 행을 의미하고, col 의 각 index 값에는 열이 저장됨
"""
while (k < i and flag):
# col[i] == col[k] -> i 번째 행과 k 번째 행의 값이 같다는 것은 같은 열에 퀸이 놓여 있다는 것
# abs(col[i] - col[k] == (i-k)) -> 모든 방향의 대각선을 검사하기 위한 조건
if (col[i] == col[k] or abs(col[i] - col[k]) == (i - k)):
flag = False
k += 1
return flag
n = int(input())
col = [0] * (n+1)
n_queens(0, col)
print(cnt)
2.2.2 문제
찾은 유투브 영상을 토대로 구현한 코드에 예제 값을 넣으면 정답을 도출하는 것을 확인했습니다. 하지만 baekjoon 에 이 코드를 제출하니 시간 초과로 인해 오답이라는 결과를 받았습니다. 아마도 n_queens 함수에서 모든 열에 대해서 확인을 하면서 백트래킹을 위해 n_queens 를 부르는 것과 현재 행에 대해서 퀸을 놓을 수 있는지 확인하는 promising 함수에서 매번 n 번 만큼 반복하기 때문에 시간 초과가 나는 것 같습니다.
2.3 다른 방식으로 접근
시간 초과 문제를 해결하기 위해 다른 방식으로 접근을 하기로 했습니다. 현재 행에 퀸을 놓을 수 있는지 확인하는 것을 $O(1)$ 시간안에 해결을 해야 하는데 이에 대한 방법으로는 같은 열에 놓을 수 있는지 체크하는 리스트와 오른쪽 아래와 왼쪽 아래 대각선에 놓을 수 있을지 체크하는 두 개의 리스트를 이용하는 방식을 이용했습니다.
즉 총 3개의 리스트를 이용해 각 리스트에 index 로 접근하는 방식을 이용했습니다. 코드는 다음과 같습니다.
def solve_n_queen(n):
cnt = 0
cols = [False] * n # 열 체크를 위한 리스트
diag1 = [False] * (2*n) # 왼쪽 아래 대각선 체크를 위한 리스트
diag2 = [False] * (2*n) # 오른쪽 아래 대각선 체크를 위한 리스트
def backtrack(row):
nonlocal cnt
# 현재 행이 마지막 행이면 cnt 하나 증가시키고 함수 종료
if row == n:
cnt+=1
return
#0부터 n-1 까지 열을 검사
for col in range(n):
# 오른쪽 아래 대각선, 왼쪽 아래 대각선, 열이 모두 False 이면 퀸을 놓을 수 있음
if cols[col] == diag1[row+col] == diag2[row-col] == False:
# 퀸을 놓고
cols[col] = diag1[row+col] = diag2[row-col] = True
# 백트래킹 진행
backtrack(row+1)
# 놓은 퀸을 제거
cols[col] = diag1[row+col] = diag2[row-col] = False
backtrack(0)
return cnt
n = int(input())
print(solve_n_queen(n))
대각선 체크를 위한 리스트이 크기를 2n 으로 하는 이유는 행과 열의 값을 더한 값이 0, 1, 2, 3, 4, 5, 6 총 7개가 될 수 있기 때문입니다. 그래서 정확하게는 2n-1 로 해야 하지만 2n 으로 해도 메모리의 여유가 충분하기 때문에 저는 2n 으로 하였습니다.
위 코드를 통해 baekjoon 에서 9663 번 문제가 맞았다는 결과를 받았습니다.
3. 마치며
baekjoon 의 백트래킹 문제인 N-Queens 문제에 대해서 알아보고 백트레킹에 대해서도 조금 공부를 해보았습니다. 저는 이전부터 경우의 수, 브루트 포스, 백트레킹 알고리즘 문제에 좀 많이 약했습니다. 그래서 특히 이번 문제를 풀면서 정말 많은 시간을 들였습니다만 혼자 풀지 못했습니다. 그래도 이번 문제를 계기로 백트레킹과 백트레킹 문제에 대해서 어느 정도 이해가 되었으며 이후에는 따로 브루트포스와 백트레킹에 대한 개념 정리에 대한 포스트로 업로드할 생각입니다. 또한 제가 부족한 문제들을 더 많이 풀어보고자 합니다. 앞으로도 이번과 같이 막히는 문제들 혹은 공부가 필요하다고 생각되는 문제들이 있다면 포스트로 정리하며 공부를 하고자 합니다. 그럼 긴 긁 읽어 주셔서 감사드리며 궁금한 사항, 잘못된 내용, 오타 등이 있을 경우 댓글로 알려주시길 바랍니다.
Comments