https://www.acmicpc.net/problem/9663

---

문제

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

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

입력

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

출력

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

풀이

이 문제는 백트래킹 문제로 유명하다.

브루탈포스로 풀 수 있지만
조건문을 걸어 탐색횟수를 효율적으로 줄일 수 있다.

https://chanhuiseok.github.io/posts/baek-1/
자세한 설명은 위 블로그에서 참고

핵심은 재귀를 통해 유망하다면 계속 진행하고
유망하지 않다면 그 전시점으로 돌아가는 것이다.

처음 1행부터 시작해서 1열에 퀸을 놓아본다.
유망하다 -> 2행으로 넘어가서 1열에 놓아본다.
1열 1열 겹치므로 유망하지않다 -> 2행 2열에 놓아본다.
대각선이 겹치므로 유망하지않다 -> 2행 3열에 놓아본다.
유망하다 -> 3행으로 넘어가서 1열에 놓아본다.
...

이런식으로 해서 행이 4행까지 넘어와서 유망하다면 count를 추가해준다.

이때,
2차원 배열로 해야할 것 같지만 1차원 배열로도 충분히 풀 수 있다.

board = [2,0,1,3] 이라면
board[0] => 2 즉, 0번째 행에 2번째 열에 퀸이 놓여져 있다는 뜻

따라서 소스코드에서 cdx가 행을 뜻하고
n_queen(0)은 0번째 행부터 시작한다고 보면 된다.

1차원 배열로 유망한지 확인하는 법은
같은 열이 있는지 확인하는 것,
행끼리의 차이와 열끼리의 차이가 같다면 대각선이 겹치는 것이된다.

소스코드

def is_promising(cdx):
    for i in range(cdx):  # cdx행 전까지 체크
        # cdx행과 그전의 행들을 비교해서 열이 같으면 위아래로 같은 것이고 행끼리 뺀값이 열끼리 뺀값이랑 같으면 대각선으로 같음
        if board[cdx] == board[i] or abs(board[cdx]-board[i]) == cdx-i:
            return False
    return True


def n_queen(cdx):
    global cnt
    if cdx == n:  # 행이 n끝까지 왔으면 가능한것 이므로 경우의 수 + 1
        cnt += 1
        return
    for i in range(n):  # i는 열
        board[cdx] = i  # 해당 행의 i번째 열에 퀸을 놓아 봄
        if is_promising(cdx):  # 유망한지 체크
            n_queen(cdx + 1)  # 유망 하면 다음 행도 확인


n = int(input())
cnt = 0
board = [-1]*n
n_queen(0)
print(cnt)

백트래킹 문제 자체가 파이썬에서는 불리한 알고리즘 영역이라 한다.
백준에서는 그래서인지 시간초과가 뜬다.
근데 똑같은 문제를 프로그래머스에서 풀면 통과하게된다.