티스토리 뷰
Approach
N Queen Problem 문제를 가장 기본적인 Deterministic Algorithm(Backtraking) 을 이용하여 풀어본 코드.
자세한 내용은 추후 정리.
Code
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
int promising(int);
void queens(int);
void print();
int* col;
int N;
FILE *output;
int main(void)
{
FILE *file;
char file_name[255];
int i;
printf("input file name?");
scanf("%s", &file_name);
file = fopen(file_name, "r");
output = fopen("output.txt", "w");
N = getc(file) - '0';
col = (int*)malloc(sizeof(int) * (N+1));
for (i = 0; i <= N; ++i)
col[i] = 0;
queens(0);
return 0;
}
int promising(int i)
{
int k;
int result;
k = 1;
result = TRUE;
while (k < i&&result)
{
if (col[i] == col[k] || abs(col[i] - col[k]) == i - k)
result = FALSE;
k++;
}
return result;
}
void queens(int h)
{
int i;
if (promising(h)) {
if (h == N) {
print();
exit(1);
}
else
{
for (i = 1; i <= N; ++i)
{
col[h+1] = i;
queens(h + 1);
}
}
}
}
void print()
{
int i;
for (i = 1; i <= N; ++i)
{
fprintf(output,"%d\n", col[i]);
}
}
'Algorithm' 카테고리의 다른 글
2751 - Heap sort (0) | 2016.12.01 |
---|---|
2665 - 미로 만들기 + 경로 출력 (0) | 2016.11.30 |
2448_별찍기 - 11 (0) | 2016.10.13 |
Matrix chain multiplication (0) | 2016.10.12 |
Floyd's Algorithm (0) | 2016.10.12 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- robocopy
- 수식
- Bit
- 안드로이드
- 비트
- mathjax
- C
- 비트연산자
- python
- syntax highlighting
- DNS
- algorithm
- Math
- Kotlin
- Matrix
- 비트마스크
- mysql
- Highlighter
- 도메인
- 행렬
- highlightjs
- 삼항연산자
- Android
- 알고리즘
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함