글 읽기 - 어디가 잘못된 걸까요 ㅠ N Queen 문제입니다

ekfrhkquf12 4년 전 0

교재에 있는거 그대로 옮겨서 구현해봤는데 어디서 틀렸는지 모르겠어요 ㅠㅠㅠ

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<stack>
using namespace std;
int count = 0;
bool promise(int k, int n, int* bt);
void backtracking(int k, int n, int* bt, int* cnt);

int main() {
	int n;
	scanf("%d", &n);
	
	int* bt = (int*)malloc(sizeof(int)*n);
	int* cnt = (int*)malloc(sizeof(int));
	*cnt = 0;
	backtracking(0, n, bt, cnt);

	printf("%d", *cnt);


}

void backtracking(int k, int n, int* bt, int* cnt) {
	
			if (promise(k, n, bt)) {
				if (k == n) {
					*cnt = *cnt +1;
					//return;
				}
				else 
					for (int j = 0; j < n; j++) {
					bt[k+1] = j;
					backtracking(k + 1, n, bt, cnt);
				}
			}
			
}

bool promise(int k, int n, int* bt) {
	
	bool flag = true;
	for (int i = 0; i < k && flag; i++) {
			if (bt[i] == bt[k])
				flag = false;
			if (abs(bt[i] - bt[k]) == k - i)
				flag = false;
		} 
	
	return flag;
}

sait2000 4년 전 0

33번 줄에서 설정하는 bt 인덱스가 1 이상 n 이하입니다. 0 이상 n 미만이 되야 맞을 것 같은데요. 그리고 k == n일 때는 promise를 호출하지 않는 게 맞을 것 같습니다.

ekfrhkquf12 4년 전 0

33번째 줄에서 bt 인덱스는 k+1으로 되는거라 for loop의 j의 범위와는 상관이 없습니다 ㅜㅜ

k == n-1일 때로 으로 설정하면 n = 8일때 92가 아니라 312가 출력이 되는데,

왜 그렇게 생각하시는지 여쭤보아도 될까요..?

djm03178 4년 전 1

j가 아니고 k+1로 접근하는 것 자체가 문제입니다. 배열의 크기를 n으로 잡았으니 인덱스는 0부터 n-1까지밖에 없는데, k가 n-1인 상태에서도 bt[k+1]에 접근하고 있으니 배열의 크기를 넘어서게 됩니다. 마찬가지로 promise에도 k == n일 때 전달되어 bt[k]에 접근하고 있으니 역시 배열의 크기를 넘어섭니다.

ekfrhkquf12 4년 전 0

감사합니다.

k+1로 접근하지 않고 k로 접근하게 해서 풀었더니 해결되었네요!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 잘못된 걸까요 ㅠ N Queen 문제입니다

ekfrhkquf12 4년 전 0

sait2000 4년 전 0

ekfrhkquf12 4년 전 0

djm03178 4년 전 1

ekfrhkquf12 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말