반응형

문제 출처 :


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(00);
    
    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