백준(BOJ) 9663 N-Queen(Python)

문제 내용

 

백트래킹 문제.

각 행마다 퀸을 하나씩 배치하는데, 이때 이전 행에 배치한 퀸의 열 번호를 토대로 현재 위치에 퀸을 배치할 수 있는 지를 판단한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
L=[0]*n
ans=0
def func2(k):
    for i in range(k):
        if L[k]==L[i] or abs(L[k]-L[i])==k-i:
            return 0
    return 1
def func(k):
    global n,ans
    if k==n:
        ans+=1
    else:
        for i in range(n):
            L[k]=i
            if func2(k):
                func(k+1)
func(0)
print(ans)

 

신촌캠프 문제.

함수형으로 안 하니까 계속 시간 초과가 터져서 좀 열받았다.

pypy로 제출해서 통과했다.