[Python] N-Queen

https://school.programmers.co.kr/learn/courses/30/lessons/12952

---

백트래킹 기본 문제라는데 전혀 기본같지 않은 난이도 왜 n-queen, n-queen 하는지 이해가 가는 알고리즘이다

유튜브 강의도 참고하고 그림도 그려보면서 이해했다

2차원 배열로 풀 것 같았는데 그냥 1차원 배열로 행은 인덱스로 생략하고 열만 보자고~~ 이런 풀이법이 있을 줄은...

그리고 풀었지만 시간 초과가 떠서 다른 사람들은 왜 시간 초과가 안 뜨나 찾아보느라 푼게 아니게 된 그런 문제

 

마지막 테케 시간초과 뜬 코드

def n_queen(graph,x,n):
    result = 0
    if x == n:
        return 1
    for i in range(n):
        graph[x] = i
        if promising(graph,x):
            result += n_queen(graph, x+1, n)
    return result
        
def promising(graph,x):
    for i in range(x):
        if graph[x] == graph[i] or abs(graph[x] - graph[i]) == abs(x-i):
            return False
    return True
 
def solution(n):
    graph = [0] * n
    return n_queen(graph, 0, n)

 

graph 변수 생성해서 안 넘기고 배열 채로 파라미터 주고 n을 파라미터로 주는 부분도 뺐더니 통과

 

def n_queen(graph,x):
    result = 0
    n = len(graph)
    if x == n:
        return 1
    for i in range(n):
        graph[x] = i
        if promising(graph,x):
            result += n_queen(graph, x+1)
    return result
        
def promising(graph,x):
    for i in range(x):
        if graph[x] == graph[i] or abs(graph[x] - graph[i]) == abs(x-i):
            return False
    return True
def solution(n):
    return n_queen([0] * n, 0)