[백준 문제] 9663번 N-Queen (파이썬)

[내 풀이]

행은 고정한채로 열을 채우는 방식을 사용
다 채운다음 대각열 확인
그러나 시간초과. 내일 다시 한번 생각해봐야겠다.

# N x N 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 문제
import sys

N = int(sys.stdin.readline())

x_lst = [i for i in range(N)]

## 다음 순열 구하기 함수
def next_perm(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] <= a[i-1]:
        j -= 1

    a[i-1],a[j] = a[j],a[i-1]

    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1

    return True

# 대각열에 있는 지 확인 함수
def check(a) :
    for i in range(N) :
        for j in range(N) :
            if i < j :
                if a[i][0] - a[i][1] == a[j][0] - a[j][1] :
                    return False
                    break
                if a[i][0] + a[i][1] == a[j][0] + a[j][1] :
                    return False
                    break
    return True

# 열은 0 부터 순서대로, 행은 순열로 돌아가는 방식 사용
sum = 0
while True:
    comb_lst = []
    for i in range(N):
        comb_lst.append([x_lst[i], i])
    if check(comb_lst) == True:
        sum += 1

    if next_perm(x_lst) == False:
        break
print(sum)

[백준 문제] 9663번 N-Queen (파이썬)

Share this post