파이썬 알고리즘 129번 | [백준 9663번] N-Queen

Yunny.Log ·2022년 2월 25일

Algorithm

목록 보기

132/318

129. N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

2022-0805 다시 풀이

행끼리의 차 == 열끼리 차의 절대값이 True면 대각선!!

https://developnote.tistory.com/70

import sys
n=int(sys.stdin.readline().rstrip())
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):
            # 행끼리의 차 == 열끼리 차의 절대값이 True면 대각선
            return False
    return True

def n_queens(x):
    global ans
    if x == n: # 마지막까지 행애 ㄷㅎ덜허묜 
        ans += 1
    else:
        for i in range(n):
            row[x] = i # x 행 i 열 
            
            if is_promising(x):
                print(i, row)
                n_queens(x+1)
n_queens(0)
print(ans)

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

def promising(i,col):
    k=1#1행부터 돌기
    chk=True
    while k<i and chk :
        if col[k]==col[i] or abs(col[k]-col[i])==i-k:
            chk=False
        k+=1
    return chk

def nq(i, col):
    global cnt
    if promising(i,col):
        if(i==n):
            cnt+=1
            #print(col[1:n+1])
        else :
            for j in range(1,n+1):
                col[i+1]=j
                nq(i+1,col)

if __name__=="__main__":
    cnt=0
    n=int(input())
    col=[0]*(n+1)
    nq(0,col)
    print(cnt)

-> 시간초과

def nq(i, col):
    global cnt
    chk=1
    for k in range(1,i):#두번째행부터 확인 가능
        if col[k]==col[i] or abs(col[k]-col[i])==i-k:
            chk=0
    if(i==n) and chk:
        cnt+=1
    elif chk :
        for j in range(1,n+1):
            col[i+1]=j#다음 행의 열을 j로 지정했을 때
            nq(i+1,col)

if __name__=="__main__":
    cnt=0
    n=int(input())
    col=[0]*(n+1)
    nq(0,col) #i의 스타트는 0으로 해야한다 그래야지 첫번째 행을 (i=1) 첨에 뽑기가 가능 
    print(cnt)

-> again 시간초과

11까지는 괜찮은데 12부터 15까지 10초가 넘게 걸림
참고 블로그

def promising(i):
    for j in range(0,i):
        # 새로운 퀸과 기존의 퀸이 같은 행에 있거나 대각선에 있을 경우
        if row[j] == row[i] or abs(row[j]-row[i]) == (i-j):
            return False
    return True
 
def N_queen(i):
    global result
    if i == N:
        result += 1
    else:
        for j in range(N):
            row[i] = j
            if promising(i):
                N_queen(i+1)
 
 
N = int(input())
row = [0]*15
result = 0
N_queen(0)
print(result)

-> 위에거 참고해서 수정했는데도 시간 초과 계속 걸리네

아래 코드 참조 블로그!

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

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

n_queens(0)
print(ans)