백준34 BOJ 9663 - N QUEEN 저번에 마구잡이로 풀어봤지만 백트래킹 연습으로 한 번 더 풀어봤다. 1번줄부터 n번 줄까지 퀸을 배치하는데, x좌표가 중복되지 않게 뽑는 것을 백트래킹 해주면서 대각선에 다른 퀸이 배치돼있는지 검사해줬다. #include #include #include #include using namespace std; int n; bool isValid(vector& picked) { //대각선 검사만 해주면 된다. |(y'-y)| == |(x'-x)| 인경우 return false if (picked.empty()) return true; for (int i = 0; i < picked.size()-1; i++) { // {i, picked[i]} : 퀸의 위치 (y,x) for (int j = i + 1; j <.. 2019. 7. 6. BOJ 15649 - N과 M (1~12) N개 중 M개를 뽑아 나열하는 경우의 수 시리즈이다. 기본적으로 백트래킹을 이용해서 재귀로 구현함. 9~12같은 경우 중복을 제거해줘야 하는데, 이건 set로 해결하였다. #include #include #include using namespace std; void printPicked(vector& picked) { for (int n : picked) printf("%d ", n + 1); printf("\n"); } int n, m; void pick(vector& picked, vector& isUsed, int k) { if (k == m) { printPicked(picked); return; } for (int next = 0; next < n; next++) { if (!isUsed[nex.. 2019. 7. 6. 이전 1 ··· 6 7 8 9 다음