Back Tracking
-
[백준 BOJ/C++] 9663 N-Queen알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 16. 00:06
9663번: N-Queen 알고리즘 공부나 코딩 테스트를 준비하는 사람들이라면 꼭 한번 풀어봐야한다고 할 수 있을만큼 백트래킹을 대표하는 유명 문제다. 컴퓨터가 등장하기 훨씬 전부터 존재했던 문제로 8*8 크기의 체스판에 8개의 퀸을 배치하는 8-Queen 문제에서 시작되었다. Chess에서 Queen은 N * N 크기의 체스판에 정확히 N개까지 서로의 이동 경로를 피해서 배치할 수 있다. 이동 방법도 복잡하지 않아서 프로그램으로 단순화해서 풀이하기도 쉬운 편이다. N의 갯수가 15 미만인 것에서 흰트를 얻는다면 모든 경우의 수를 직접 따져봐야함을 알 수 있다. 하지만 이 문제를 처음 접하면 백트랙킹이나 브루트 포스에 대해 알고있더라도 막상 Queen을 놓는 상황과 앞서 놓은 Queen과의 위치 확인을 ..