n-queen
-
[백준-9663]-[백트래킹] - N-Queen알고리즘/백트래킹 2018. 11. 21. 18:00
문제 링크 : https://www.acmicpc.net/problem/9663 이 문제는 백트래킹 알고리즘의 기본적인 예제라고 한다. 백트래킹 알고리즘은 그리디 알고리즘과 모든 가능성을 조회하고 조회 한 값으로 결과를 구한다는 비슷한 성질을 가진다. 차이점은 그리디 알고리즘은 정말 모든 가능성을 조회하지만 백 트래킹의 경우는 다음경우가 유효한 경우가 아니면 진행하지 않는다. 그런 개념을 이해할 수 있는 문제가 N-Queen 문제인거 같다. 이 문제는 퀸을 N x N 체스 판에 N 개만큼 위치 시킬 수 있는 경우의 수가 얼마만큼 있는지 구하는 문제이다. 예로 4 x 4 체스판에 (1, 2) 위치에 퀸이 놓여져 있다고 가정하면 (1번 인덱스가 제일 앞 인덱스라 할 때) Q 위의 빨간색인 부분에는 퀸을 놓을..