백준(9663) - N-Queen

올랜도·2022년 6월 2일
0

N-Queen 문제이다.
카테고리상 DFS와 백트래킹 그리고 완전탐색에 분류되며 백트래킹의 대표격이 되는 문제이다.

본인은 재귀, 그래프에 상당히 취약한 스타일로 일단 유튜브, 블로그 등을 탐방하며 백 트래킹에 대한 틀을 잡고 문제를 풀었다.

일단 N-Queen이라 함은 n x n만큼의 크기를 갖는 체스판에 n개의 퀸을 두되, 서로가 간섭할 수 없는 위치에 퀸을 두는 것을 의미한다.

따라서 현재 위치에 퀸을 두고 다음 위치에 퀸을 둘 수 있는가 없는가를 확인하기 위해 promising(idx) 함수를 사용하여 검증 후 반환값에 따라 다음 순서로 진행하도록 하며 이 과정을 가지치기 단계라고 본다.

만약 갈수 없음에도 불구하고 진행하게 된다면 모든 경우의 수를 확인해야 하기 때문에 효율적인 측면에서 이렇게 가지치기를 수행하는 것이다.


문제를 해결하기 위해 두개의 함수로 진행이 된다.
1. dfs(idx)

  • 일반적으로 구현하는 dfs 와 큰 차이가 없다.
    재귀를 통한 구현 수행
def dfs(idx):
	# 전체 순회를 마쳤는가?
    if idx == n:
        global result
        # 같을 경우 결과값 추가
        result += 1
        return
    
    for i in range(n):
    	# 현재 위치를 저장
        board[idx] = i
        # 다음 위치에 퀸을 둘 수 있는가를 확인하기 위한 promising함수 수행
        if promising(idx):
            dfs(idx + 1)

  1. promising(idx)
  • 다음으로 넘어 갈 수 있는가를 확인하기 위한 검증 과정으로
    매개변수로 들어온 idx가 조건을 만족할 경우에 대해서 참값을 반환하도록 구성
def promising(idx):
    for i in range(idx):
        if board[idx] == board[i] or abs(board[idx] - board[i]) == abs(idx - i):
            return False
    
    return True

전체 코드

import sys

n = int(sys.stdin.readline())

board = [0] * n
result = 0
def promising(idx):
    for i in range(idx):
        if board[idx] == board[i] or abs(board[idx] - board[i]) == abs(idx - i):
            return False
    
    return True


def dfs(idx):
    if idx == n:
        global result
        result += 1
        return
    
    for i in range(n):
        board[idx] = i
        if promising(idx):
            dfs(idx + 1)

dfs(0)
print(result)
profile
☂️생존주의 개발자

0개의 댓글