Back Tracking - N QueenCSE 학부/알고리즘2024. 2. 14. 21:56
Table of Contents
Back Tracking
- = 전부 다 찾아보기
- systematic 순서
- cut off : 도저히 답 안나올거 같으면 그만두기
N-Queen
- N * N 크기 체스판에 N개의 퀸을 서로 공격할 수 없도록 올려놓는 경우의 수
- 퀸 : 8방향 공격 가능
N=8 기준
체스판 자리가 총 64개 이므로
64C8 의 놓을 수 있는 경우의 수가 존재하는데, 서로 공격하면 안되므로 제외되는 게 있다.
1. 한 row에 퀸이 2개 들어갈 수는 없다. 같은 row에 있으면 그 방향으로 공격 가능하므로
2. 아래로 내려갈 수록 위 퀸의 대각선 아래랑, 바로 밑은 제외되므로, 점점 놓을 수 있는 자리가 적어진다.
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
'CSE 학부 > 알고리즘' 카테고리의 다른 글
| State Space - 15 Puzzle, Subset Sum Problem (0) | 2024.02.14 |
|---|---|
| Pseudo Polynomial - 동전 문제, 막대기 자르기, 합 분해 (0) | 2024.02.14 |
| Graph - SCC (0) | 2024.02.01 |
| Graph - Topological Sort (0) | 2024.02.01 |
| Graph - BCC (0) | 2024.02.01 |
@체리비! :: 체리비 Lab。
틀린 부분은 언제든지 말씀해주세요!!! 감사합니다!