N-Queen1 [백트래킹] N-Queen문제 백트래킹이란? 해를 찾기 위해 DFS방식으로 탐색하다가 해당 루트가 유망한지(Promising) 검사하여 조건이 맞지 않다면 가지치기(Pruning)하고 다른 루트로 돌아가 최적의 해를 찾는 방법이다. 상태 공간 트리(State Space Tree) 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리이다. N-Queen문제 대표적인 백트레킹 문제이다. 백준 9663번 문제: https://www.acmicpc.net/problem/9663 n = int(input()) row = [250] * n answer = 0 #현재 레벨에서 놓을 수 있는지 없는지 체크하는 함수 (행[자동 생략], 열, 대각선) def can(level): for i in range(level): if row[level] =.. 2021. 12. 28. 이전 1 다음