backtracking1 Backtracking이란 무엇인가? 백트래킹(Backtracking) 일반적인 알고리즘이다. 백트래킹은 CSP(Constrain Staisfaction Problems)을 해결하기 위해 쓰인다. 백트래킹은 모든 조합의 수를 조건이 만족할 때 살펴본다. N-Queen문제에서 많이 사용된다. N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 4 * 4 기준으로 문제를 풀어보자. 퀸은 칸을 기준으로 오와 열, 대각선 이동이 가능하다. 첫 번째 퀸과 공격할 수 없게 배치할려면 2번째 줄은 3, 4번째 위치에 퀸을 놓아야 한다. 첫 번째 퀸의 위치를 (1, 1)로 하면 트리구조는 다음과 같다. 만약 이문제를 가지치기 하지않는 DFS로 풀이했다면 유망하지 .. 2021. 8. 4. 이전 1 다음
