N-Queen

 

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

프로그래머스

 

나의 풀이

# 2024-07-14
import copy
def ch_board(board, row, col, n):
    for i in range(row+1, n):
        board[i][col]=1
        if 0<=col-(i-row)<n:
            board[i][col-(i-row)]=1
        if 0<=col+(i-row)<n:
            board[i][col+(i-row)]=1
    return board

def dfs(board, row, n):
    answer=0
    if row==n:
        return 1
    for i in range(n):
        if board[row][i]==0:
            cp_board=[row[:] for row in board]
            answer+=dfs(ch_board(cp_board, row, i, n), row+1, n)
    return answer 

def solution(n):
    board = [[0]*n for _ in range(n)]
    
    answer = dfs(board, 0, n)
    return answer

 

시간 복잡도

각 행에서 최대 n개의 열을 시도하고, 각 시도마다 dfs를 재귀 호출
시간 복잡도는 O(n!)

 

 

수정 코드(시간 단축, 리팩토링)

def dfs(n, now_row, d_set, ld_set, rd_set):
    answer = 0
    if now_row == n:
        return 1
    else:
        for now_col in range(n):
            if (now_col in d_set) or (now_row-now_col in ld_set) or (now_row+now_col in rd_set):
                continue
            d_set.add(now_col)
            ld_set.add(now_row-now_col)
            rd_set.add(now_row+now_col)
            answer+=dfs(n, now_row+1, d_set, ld_set, rd_set)
            d_set.remove(now_col)
            ld_set.remove(now_row-now_col)
            rd_set.remove(now_row+now_col)
    return answer

def solution(n):
    answer=dfs(n, 0, set(), set(), set())
    return answer

 

세로, 대각선 관련 집합을 통해 생성 불가능한 큐의 위치는 가지치기!!!!