[백준 9663] N -Queen

N-Queen 성공

시간 제한메모리 제한제출정답맞힌 사람정답 비율

10 초

128 MB

151065

74489

47777

47.571%

문제

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

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

입력

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

출력

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

예제 입력 1 

8

"""
1. 아이디어
N-Queen
같은행을 기준으로
col, 대각선으로는 놓으면 안되고
나머지 경우의 수
2. 시간복잡도
N<14 : O(N!) 불가능
해시테이블로 최대한 경로를 찾아야함
찾기
1. col 인지
2. 대각선(/) col+row
3. 대각선(\\) col-row+N-1
3중 하나라도 True 이면 안됨

"""

import sys


def main():
    input = sys.stdin.readline
    N = int(input())
    cnt = 0

    # 해쉬테이블 - 시간 단축
    col_used = [False] * N
    diag1_used = [False] * (2 * N - 1)
    diag2_used = [False] * (2 * N - 1)

    def bt(row):
        nonlocal cnt

        if row == N:
            cnt += 1
            return

        for col in range(N):
            d1 = row + col
            d2 = row - col + N - 1

            if col_used[col] or diag1_used[d1] or diag2_used[d2]:
                continue

            col_used[col] = True
            diag1_used[d1] = True
            diag2_used[d2] = True

            bt(row + 1)

            col_used[col] = False
            diag1_used[d1] = False
            diag2_used[d2] = False

    bt(0)
    print(cnt)


main()

예제 출력 1 

92

출처

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

---