[파이썬] 9663. N-Queen

문제

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

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

입력

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

출력

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

예제 입력 1 

8

예제 출력 1 

92

 

 

🔥 나의 풀이

# N * N인 체스판에서 N개의 퀸이 가로 or 세로 or 대각선으로 서로 공격할 수 없게 놓는 방법의 수를 구하는 문제
# 백트래킹
# 이전에 놓은 퀸과 대각선으로 위치하면 return
# visit을 N개 만큼 열을 만들고 값으로 행을 넣는다
N = int(input())
visit = [-1] * N
answer = 0

# 이전에 놓은 퀸들과 대각선 검사
def check(depth) :
    cur = visit[depth-1]
    cnt = 1
    for i in range(depth-2, -1, -1) :
        if cur - cnt == visit[i] or cur + cnt == visit[i] :     # 왼쪽 위 or 오른쪽 위에 같은 행이 있을 때
            return False
        cnt += 1
    return True

def dfs(depth) :
    global answer

    if depth > 1 and not check(depth) :     # depth개의 퀸이 서로 공격할 수 있다
        return

    if depth == N :
        answer += 1
        return

    for i in range(N) :
        if i not in visit :     # 서로 다른 N개의 행
            if visit[depth] == -1 :
                visit[depth] = i
                dfs(depth + 1)
                visit[depth] = -1

dfs(0)
print(answer)       # 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수

백트래킹 풀이

pypy3로 제출해서 통과했다!

 

 

🌿 다른 사람 풀이

# https://seongonion.tistory.com/103
n = int(input())

ans = 0
row = [0] * n

def is_promising(x) :
    for i in range(x) :
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i) :
            return False
    return True

def n_queens(x) :
    global ans
    if x == n :
        ans += 1
        return
    else :
        for i in range(n) :
            # [x, i]에 퀸을 놓겠다.
            row[x] = i
            if is_promising(x) :
                n_queens(x + 1)

n_queens(0)
print(ans)

이 풀이도 pypy3로 제출해야 통과한다.

행 끼리의 차와 열 끼리의 차가 같으면 대각선에 있다.

is_promising 메서드를 실행해서 퀸이 서로 공격하지 않으면 재귀호출한다.

 

 

문제 출처 👉 백준