자바로 만드는 백트래킹 (Backtracking) + n queens 문제
백트래킹 알고리즘이란 모든 경우의 수를 검색하는 알고리즘 입니다."특정조건"을 만족하는 모든 경우의 수를 찾고 싶을 때 사용하면 유용해요. 백트래킹을 활용해서 풀 수 있는 대표적인 알고리즘 문제로 N Queens 문제가 있습니다. N-Queens Problem문제를 간단하게 설명하자면 N*N 체스판에 N개의 Queen들이 "서로 공격 받지 않게" 놓는 위치를 구하는 것 입니다! 공격받지 않는 위치에 놓는 다는게 무슨 말일까요?퀸 하나를 놓았을 때입니다.퀸은 자신의 상하좌우를 공격할 수 있고, 대각선 방향도 공격할 수 있습니다. 만약에 퀸을 하나 더 놓아서 서로 공격 받지 않게 놓으려면 어떻게 해야 할까요? 그림처럼 체크한 곳중 한 곳에 퀸을 놓으면 서로 공격받지 않게 되겠죠? 이제 문제의 의도는 알았으니..
프로그래밍/알고리즘
2016. 12. 15. 22:25