[백트래킹] N-Queen문제

[백트래킹] N-Queen문제

728x90

반응형

백트래킹이란?

해를 찾기 위해 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] == row[i] or abs(row[level] - row[i]) == level - i: #열위치가 같은 조건 | 열위치 차이와, 행위치 차이가 같다면 대각선 return False return True def dfs(level): global answer if level == n: answer += 1 return else: for i in range(n): #퀸을 배치할 열 row[level] = i #퀸을 level행 i열에 배치 if can(level): dfs(level + 1) dfs(0) print(answer)

참고자료: https://www.fun-coding.org/Chapter21-backtracking-live.html

이해자료: https://chanhuiseok.github.io/posts/baek-1/

728x90

반응형

from http://lagooni.tistory.com/134 by ccl(A) rewrite - 2021-12-29 02:00:55