프로그래머스 N-QUEEN 코드 및 해설 (파이썬)

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

코딩테스트 연습 - N-Queen

 

항상 한 행에 하나의 퀸만 놓을 수 있으므로 첫 번째 행부터 차례대로 퀸을 놓고, 그 퀸이 공격할 수 있는 범위가 아닌 다음 행의 위치에 다음 퀸을 위치하는 방법으로 풀이했습니다.

attackRange 함수는 현재 퀸의 위치와 n을 입력받으면, 그 퀸이 공격할 수 있는 범위를 반환합니다. 이때 첫 번째 행부터 순서대로 내려가며 퀸을 위치시키기 때문에 현재 행이나 그 이전 행의 공격 범위는 계산하지 않도록 했습니다.

이후 __help라는 recursive 함수를 통해 현재 행에서 퀸을 놓을 수 있는 위치(possible_pos)를 탐색하고, 각 위치에 대해 다시 __help 함수를 호출하여 또 그 다음 행에 퀸을 놓을 수 있는지 확인하도록 했습니다. 이때 모두 공격 가능한 범위라 현재 행에 퀸을 놓을 수 없거나, 현재 행이 마지막 행일 때 이 함수에서 빠져나오도록 했습니다.

이 __help 함수를 첫 번째 행에서 퀸의 위치를 (0,0) ~ (0,n//2-1) 까지 일 때 각각 실행했습니다.
게임 보드가 정사각형이기 때문에 절반까지만 탐색해도 좌우대칭에 의해 2를 곱해주어 최종 답을 반환하면 됩니다.
단, n이 홀수일 땐 퀸의 위치가 정가운데인 (0,2//n) 일 때의 경우도 더해주어야 합니다.

 

 

 

# n = 12일 때 시간 초과

def attackRange(position, n):
    result = []
    x,y = position
    
    # 퀸이 속한 행 
    # result += [(x,i) for i in range(n)] 
    
    # 퀸이 속한 열 
    result += [(i,y) for i in range(x+1, n)] 
    
    # 퀸의 대각선 (오른쪽 아래)
    while (x+1) in range(n) and (y+1) in range(n):
        result.append((x+1,y+1))
        x += 1
        y += 1 
    
    # x,y = position
    # 퀸의 대각선 (왼쪽 위)
    # while (x-1) in range(n) and (y-1) in range(n):
    #    result.append((x-1,y-1))
    #    x -= 1
    #    y -= 1 

    x,y = position
    # 퀸의 대각선 (왼쪽 아래)
    while (x+1) in range(n) and (y-1) in range(n):
        result.append((x+1,y-1))
        x += 1
        y -= 1 
    
    # x,y = position
    # 퀸의 대각선 (오른쪽 위)
    # while (x-1) in range(n) and (y+1) in range(n):
    #    result.append((x-1,y+1))
    #    x -= 1
    #    y += 1 

    return list(set(result))

def __help(pos, n, attacked, answer):
    x,y = pos
    
    # 마지막 행이면 
    if x == (n-1):
        return answer + 1
    
    # 다음 행 중 공격 범위에 없는 위치
    possible_pos = [(x+1, i) for i in range(n) if (x+1, i) not in attacked + attackRange(pos, n)]
    
    # 공격 범위에 없는 다음 행의 모든 위치들에 대해 
    for pp in possible_pos:
        answer = __help(pp, n, attacked + attackRange(pos, n), answer)
    
    # 공격 범위가 아닌 다음 행 위치가 없으면 
    if not possible_pos:
        return answer
    
    return answer
    

def solution(n):
    answer = 0

    for i in range(n//2):
        attacked = []
        # 첫 번째 퀸을 (0,0) ~ (0,n)까지 놓아보기 
        answer = __help((0,i), n, attacked, answer)
    

    # 짝수 (좌우대칭)
    if n % 2 == 0:
        return answer * 2 

    # 홀수 (좌우대칭 + 가운데)
    return answer * 2 + __help((0,n//2), n, [], 0)