반응형
문제 출처 :
https://www.acmicpc.net/problem/9663
알고리즘 분석 :
문제 해결에 필요한 사항
1. 백 트래킹
백 트래킹을 기반으로 풀 수 있는 문제이다.
퀸이 놓였을 때, 지금 퀸이 움직일 수 있는 위치에 모두 못 놓는 조건은
1. 현재 퀸과 같은 열에 두려 할 때
2. 대각선(1)이 공유 될 때 ↙
3. 대각선(2)이 공유 될 때 ↘
다음과 같이 대각선을 넘버링하고, 대각선이 공유되는지, 같은 열이 공유되는지는 아래 코드와 같이 작성하였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | for (int i = 0; i < n; i++) { if (row[i] || dia1[y + i] || dia2[n - i + y - 1]) continue; row[i] = true; dia1[y + i] = true; dia2[n - i + y - 1] = true; dfs(y + 1, cnt + 1); row[i] = false; dia1[y + i] = false; dia2[n - i + y - 1] = false; } |
for문의 i는 x좌표를 의미하고 있고 그 i위치에 두려 할 때 어떠한 공유도 없다면
dfs(다음 행, 퀸 개수);로 움직인다.
(사실 cnt와 y의 개념이 같기 때문에 cnt를 지워도 된다.)
소스 코드 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <iostream> #include <cstdio> #include <cmath> using namespace std; int n; bool dia1[40]; bool dia2[40]; // bool col[20]; bool row[20]; int ans; void dfs(int y, int cnt) { if (cnt == n) { ans++; return; } for (int i = 0; i < n; i++) { if (row[i] || dia1[y + i] || dia2[n - i + y - 1]) continue; row[i] = true; dia1[y + i] = true; dia2[n - i + y - 1] = true; dfs(y + 1, cnt + 1); row[i] = false; dia1[y + i] = false; dia2[n - i + y - 1] = false; } } int main() { scanf("%d", &n); dfs(0, 0); cout << ans; return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[13265번] 색칠하기 (0) | 2017.05.01 |
---|---|
[1219번] 오민식의 고민 (7) | 2017.04.30 |
[1377번] 버블 소트 (0) | 2017.04.27 |
[1915번] 가장 큰 정사각형 (0) | 2017.04.26 |
[1213번] 팰린드롬 만들기 (0) | 2017.04.26 |