티스토리 뷰
728x90
https://www.acmicpc.net/problem/9663
백트래킹 C++
백트래킹의 고전 문제 N-Queen 문제이다. 아무리 그래도 규칙 설명 한 줄이 없다.
접근방법
알고리즘 수업 때 배운 로직을 사용했다.
각 행에 퀸이 놓여있는 열 인덱스를 담은 col 배열을 전역변수로 선언해두고
한 행 안에서 각 열에 대한 반복문을 돌면서 퀸을 놓고 함수를 재귀 호출한 뒤
다시 퀸을 거두면서 백트래킹을 구현했다.
promising을 함수 초반에 호출하여 검사하는게
직관적으로 와닿지 않아서 퀸을 놓기 직전에 promising을 호출하는 방법으로
다시 구현했다.
퀸을 일단 놓고 공격받지 않는지 검사한 뒤 공격받지 않으면 그대로 놓은 상태에서
queen함수를 재귀호출한다. 이후 퀸을 다시 거두면서 백트래킹한다.
그럼 promising함수를 더 많이 호출하게 되는게 아닌가 싶었지만
queen함수를 그 만큼 덜 호출하게 된다.
되게 미세하지만 시간도 줄고 코드도 줄었다. (코드 왜 줄었지..?)
promising 함수는 같은 열에 퀸이 있는지, 대각선에 퀸이 있는지를 검사했다.
소스코드
#include <iostream>
using namespace std;
int N;
int col[15] = {0,};
int result = 0;
bool promising(int row){
for(int r = 0 ; r < row ; r++){
if(col[r] == col[row] || abs(col[row]-col[r]) == row - r)
return false;
}
return true;
}
void queen(int cnt){
if(cnt == N){
result++;
}
for(int c = 0 ; c < N ; c++){
col[cnt] = c;
if(promising(cnt)){
queen(cnt+1);
}
col[cnt] = 0;
}
}
int main(){
cin >> N;
queen(0);
cout << result;
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 1312] 알고리즘 33일차 : 소수 (0) | 2020.07.29 |
---|---|
[백준 3036] 알고리즘 32일차 : 링 (0) | 2020.07.28 |
[백준 9375] 알고리즘 30일차 : 패션왕 신해빈 (0) | 2020.07.26 |
[백준 1912] 알고리즘 29일차 : 연속합 (0) | 2020.07.24 |
[백준 10828] 알고리즘 28일차 : 스택 (0) | 2020.07.22 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 다이나믹프로그래밍
- 브루트포스
- 정렬
- 웹크롤링
- 프로그래머스
- 투포인터
- 트리
- BFS
- 동적계획법
- 그리디알고리즘
- 자바
- 우선순위큐
- 가장 큰 수 프로그래머스
- 파이썬
- dp
- 스택
- 가장 큰 수 Swift
- Swift
- 최단경로
- 최대힙
- 최소힙
- 백준
- dfs
- 알고리즘
- 이분탐색
- 토마토
- 수학
- 게임이론
- c++
- 백트래킹
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함