9663
-
BOJ 9663 : N-Queen백준 문제풀이/etc 2020. 5. 19. 12:50
문제 문제 풀어보기 풀이 퀸을 먼저 배치하고 가능한 경우인지 판단하는 알고리즘을 하면 시간 초과로 문제를 풀 수 없었습니다. 그래서 다른 분의 블로그를 참조해서 백트래킹을 사용했습니다. 간단히 설명하자면 퀸을 하나 넣고 퀸의 이동반경을 모두 덱에 넣습니다. 퀸이 들어갈수 있는 곳에 넣으면서 계속 덱에 넣다 보면 퀸의 수가 N 개 이면서 덱의 사이즈가 N * N 이 되는 경우가 생깁니다. 바로 이경우가 퀸을 N 개 위치시킨 경우가 됩니다. 코드 #include #include #include #define safe(x,y) x>=0&&x=0&&y < n using namespace std; int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,-1,..