[Baekjoon] 9663_N-Queen #3

Thumb Nail

N - Queen 문제 중 한 종류인 8-Queen 문제이다.

N - Queen 문제는 결국 n을 입력받아 n * n 사이즈 보드 안에 n개의 퀸을 겹치지 않고 배열할 수 있는 경우의 수가 얼마나 되는지를 세는 알고리즘이다.

---

문제

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

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

입력

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

출력

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

---

예시 입력과 출력은 다음과 같다.

이외에도 표로 나머지 경우를 정리하면 다음과 같다.

n	1	2	3	4	5	6	7	8
경우의 수	1	0	0	2	10	4	40	92

이외에도 9, 10 등이 있지만 모든 경우의 수를 다 보여줄 필요는 없기에 일단 n이 증가한다고 해서 꼭 경우의 수도 증가하지만은 않는다는 점만 기억하면 될 것 같다.

 

먼저 내가 저번 구현 때 실수했거나 아쉬웠던 점은

1. 2차원 리스트로 보드 전체를 구현한 것 - 다른 알고리즘 풀이 블로그에서는 보드의 정보를 1차원 리스트에 y좌표를 담아 2차원을 표현했다. 알고리즘 문제를 풀 때 정보를 최대한 간소화시켜 표현하는 방법이 중요함을 깨닫게 되었다.

 

2. 전체를 다 확인하지 않고 일부만 확인하는 것 - 이것도 보드를 1차원 리스트로 옮기면서 생각해 낸 아이디어인데, 백트래킹을 할 때 굳이 보드 전체를 다 확인할 필요는 없다. 내 이동 방향이 우측이라면, 놓고 있는 열의 좌측만 확인해주면 된다. 우측에 남은 열은 그때 가서 좌측에 있는 정보만 확인하는 것으로 최적화가 가능하다.

 

알고리즘 문제를 푸는 의의는 결국 '최적해'에 가장 가까운 답을 찾는 것이다.

문제를 풀면서 끊임없이 이 알고리즘이 과연 정말 효율적인 알고리즘인지 여러 번 생각해보는 습관을 들여야겠다.

 

전체 알고리즘은 다음과 같다.

1. n 입력
2. 백트래킹 함수 시작
3. cnt 출력

백트래킹 함수의 알고리즘은 다음과 같다.

1. index 인자 입력
2. if) index < n이면 현재 열을 -1로 초기화.
3. else) cnt를 1 증가시키고(index == n일 경우임) 마지막 열을 -1로 초기화시키고 함수를 반환한다.
4. n번동안 0부터 n개의 수를 i값에 담아 반복한다.
5. i가 현재 열보다 왼쪽에 있는 열에 없는지 확인한다.
6. index번동안 반복하며 현재 열보다 왼쪽에 있는 열의 대각선에 같은 숫자가 있는지 확인한다. 열의 인덱스 차이와 y좌표 차이에 각각 절댓값을 씌운 값이 같다면 대각선에 있는 것이다.
그리고 그 칸의 숫자가 -1보다 큰지 검사한다.(이건 아마 필요 없음, index랑 다른 지도 비교 안 해도 될 듯)
7. 만약 대각선에도 수가 없다면 현재 열에 i를 추가하고 다음 index로 함수를 호출한다.

정보를 이렇게 표현할 수 있는 방법이 있다는 것을 알게 되었다.

다양한 표현 방법을 접하고, 또 현재의 표현 방법이 최선인지를 항상 생각해야겠다.

 

전체 코드는 다음과 같다.

# 9663 nQueen
n = int(input())
cnt = 0
board = [-1] * n
#print(board)
def backtracking(index):
    global board, n, cnt
    if index < n:
        board[index] = -1
    else:
        cnt += 1
        #print(board)
        board[-1] = -1
        return
    for i in range(n):
        if i not in board[:index]:
            diagonal_ck = 0
            for j in range(index):
                if j != index and abs(j - index) == abs(board[j] - i) and board[j] >= 0:
                    diagonal_ck += 1
                    break
            if diagonal_ck == 0:
                board[index] = i
                backtracking(index + 1)
    return

backtracking(0)
print(cnt)