N-queen (lv2)

문제

코딩테스트 연습 - N-Queen | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

풀이

퀸을 열에 하나씩 놓아 보며 DFS로 푸는 방법, permutations로 먼저 row와 col이 겹치지 않는 모든 경우를 구해놓고 푸는 방법 두가지를 모두 시도해봤지만, permutations로 푸는 방법은 시간초과가 난다. 사실 당연하다면 당연한데, permutaions로 접근해도 결정적으로 이전에 놓인 퀸들에 대해서 대각선 위치에 놓이는지 확인하는 시간이 O(K)만큼 걸리는것을 해결하지 못하기 때문이다. 그나마 퀸을 하나씩 놓으며 DFS로 풀면 permutations 처럼 모든 경우를 다 구해놓고 순회하지는 않아도 되기 때문에 아슬아슬하게 시간안에 실행되는 것으로 생각된다. 

DFS

answer = 0
board = []

def dfs(cnt,n):
    global answer
    if cnt == n:
        answer += 1
    for vertex in range(n):

        for i,v in enumerate(board):
            if vertex == v or cnt-i == abs(vertex-v):
                break
        else:
            board.append(vertex)
            dfs(cnt+1,n)
            board.pop()
    
def solution(n):
    dfs(0,n)
    return answer

Permutations (그래프) - 시간 제한 실패

from itertools import permutations

def solution(n):
    answer = 0
    
    for case in permutations(range(n),n):
        for i,v in enumerate(case):
            for j,w in enumerate(case[:i]):
                if abs(i-j) == abs(v-w):
                    break
            else:
                continue
            break
        else:
            answer += 1

    return answer

from itertools import permutations

def get_blocked(row,col,n):
    i = 1
    result = set()
    while row + i < n and (col + i < n or col - i >= 0):
        if col + i < n:
            result.add((row+i,col+i))
        if col - i >= 0:
            result.add((row+i,col-i))
        i += 1
    return result

def solution(n):
    answer = 0
    for case in permutations(range(n),n):
        blocked = set()
        for i,v in enumerate(case):
            if (i,v) in blocked:
                break
            blocked = blocked | get_blocked(i,v,n)
        else:
            answer += 1

    return answer