문제

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

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

www.acmicpc.net/problem/9663

  • 입력

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

  • 출력

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

최종 코드

스터디원들 말로는 백트래킹 기본 문제라서 보통 알고리즘 시간에 풀어본다는데 왜 나는 처음 풀어보는 걸까^^ㅜㅜㅜㅜ.

우선 기본적으로 체스판에서 퀸이 움직이는 룰을 알아야 문제를 풀 수 있다. 퀸은 행, 열, 대각선으로 이동할 수 있기 때문에 하나의 행과 열, 대각선에 하나의 퀸만 존재해야 한다.

따라서 각 행에 퀸을 하나씩 놓으면서 놓을 수 없는 칸이면 다시 돌아가는 백트레킹으로 문제를 풀어야 한다.

일단 퀸의 위치를 표현하기 위해 row 배열을 사용했다. 2차원으로도 표현할 수 있지만 1차원으로도 가능하다. 예를들어 3행의 5열에 퀸이 존재한다면 row[3] = 5가 되는 것이다.

그리고 각 행의 열을 돌면서 이 칸에 퀸을 놓을 수 있는지를 검사한다. 우선 row 배열의 값이 같은 게 있다면 같은 열에 퀸이 있다는 말이므로 해당 칸은 불가능하다.

그리고 대각선을 검사해야 하는데 이를 검사하기 위해서는 같은 대각선에 놓여있다면 |행 - 행| == |열 - 열|이라는 사실을 이용한다. 예를들어 [1, 4]과 [3, 2]은 |1 - 3| = |4 - 2| = 2으로 두 좌표의 행과 열 값의 차이가 같다.

더 자세한 건 아래 코드와 주석, 참고 사이트를 확인하자.

import sys

def bt(depth):
    global cnt
    # n개의 말을 전부 놓았다면 cnt += 1 한 뒤 return
    if depth == n:
        cnt += 1
        return

    # depth 행의 0부터 n-1까지의 열을 돌면서 퀸을 놓을 수 있는 칸을 찾는다.
    for i in range(n):
        row[depth] = i
        flag = 0
        # 0부터 depth-1까지의 행을 돌면서 이 칸에 퀸을 놓을 수 있는지 열과 대각선을 검사한다.
        for j in range(depth):
            if row[j] == row[depth] or abs(row[depth] - row[j]) == depth - j:
                flag = 1
                break
        # 이 칸에 퀸을 놓을 수 있다면 bt 함수를 호출한다.
        if flag == 0:
            bt(depth+1)


n = int(sys.stdin.readline())
cnt = 0
row = [0] * n
bt(0)
print(cnt)

Enhanced

좀 더 빠른 방법은 0부터 depth-1까지의 행을 돌면서 이 칸에 퀸을 놓을 수 있는지 열과 대각선을 일일이 검사하는 대신 diag1, diag2 배열을 통해 한 번에 검사하는 것이다.

이 방법은 같은 대각선에 있는 좌표는 x+y가 같거나(오른쪽 위로 향하는 대각선인 경우) x-y가 같은 속성(오른쪽 아래로 향하는 대각선인 경우)을 같는다는 점을 이용한 것이다.

예를 들어 [2, 4]을 기준으로 봤을 때 오른쪽 위로 향하는 대각선상에 있는 [5, 7]은 2 - 4 = 5 - 7 = -2로 같다. 또 오른쪽 아래로 향하는 대각선상에 있는 [3, 3]는 2 + 4 = 3 + 3 = 6으로 같다.

import sys

def bt(depth):
    global cnt

    if depth == n:
        cnt += 1
        return

    for i in range(n):
        if col[i] or diag1[i + depth] or diag2[i - depth + n - 1]:
            continue

        col[i] = True
        diag1[i + depth] = True
        diag2[i - depth + n - 1] = True
        bt(depth + 1)
        # 백트래킹 후에 다시 값을 False로 바꿔줌
        col[i] = False
        diag1[i + depth] = False
        diag2[i - depth + n - 1] = False

n = int(sys.stdin.readline())
cnt = 0
col = [False] * n
diag1 = [False] * ((n-1) * 2 + 1) # 오른쪽 위 대각선 x + y
diag2 = [False] * ((n-1) * 2 + 1) # 오른쪽 아래 대각선 x - y + n - 1
bt(0)
print(cnt)

참고 사이트