티스토리 뷰
문제 링크: https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
먼저 문제를 풀기 전 알아야 할 규칙이 있다. 퀸은 동서남북 그리고 대각선 방향 양방향 모두 이동이 가능하다.
이 조건에 만족하는 퀸 8 분이 모두 위치하기 위해서는 각 퀸 분들은 2개 이상의 퀸이 같은 행 또는 열 또는 대각선에 존재하면 안 된다. 이 퀸들이 해당하는 위치는 배열을 이용하여 받았다. 행을 i 열을 j 대각선 은 / 또는 \ 이 있다. 대각선 친구들은 [ i+ j ] 그리고 [ i - j + N]으로 나타 낼 수 있다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
각 행 또는 열 / 또는 \ 를 방문한 적이 있다면 1 처리를 해주면 된다.
다 돌았는데 cnt 값이 만약 N 이면 모든 퀸을 겹치는 부분 없이 배치해준 것이므로 ans 값을 1 증가시켜준다.
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
|
#include<iostream>
using namespace std;
int r[15];
int l[15];
int lx[30];
int rx[30];
int N;
int ans;
void dfs(int i , int cnt)
{
int j;
if(cnt == N)
{
ans++;
return ;
}
for(j=0 ; j< N ; j++)
{
if( !r[i] && !l[j] && !lx[i+j] && !rx[ i - j + N ] )
{
r[i] = l[j] = lx[i+j] = rx[ i - j + N ] = 1 ;
dfs(i+1 , cnt +1);
r[i] = l[j] = lx[i+j] = rx[ i - j + N ] = 0 ;
}
}
}
int main()
{
cin >> N;
dfs(0,0);
cout << ans ;
return 0 ;
}
|
cs |
'백준 (BOJ) > 백트래킹' 카테고리의 다른 글
백준)1759-암호 만들기 (0) | 2019.05.01 |
---|---|
백준)1987-알파벳 (2) | 2019.04.29 |
백준)6603-로또 (0) | 2019.04.28 |
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 그래프
- JavaSwing
- HTML
- php
- A
- stri
- 라오킹전사
- #스페인어 #스페인어인강 #스페인어공부 #시원스쿨스페인어
- 정렬
- 다익스트라
- 그리디
- KVK4
- 백트래킹
- 백트레킹
- greedy
- 라이즈오브킹덤즈
- BFS
- 사이클
- 사이크
- 플로이드
- CSS
- 이분 매칭
- 그리디알고리즘
- 이분매칭
- dfs
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함