NQUEEN문제에서 코드 문제점 찾아주실분..있습니까?(전체코드 올림)

  • leesm
    leesm

    트리형식으로 코드 짜는게 처음이라 감이 안잡힙니다.

    현재 코드 이렇습니다. 도저히 뭐가 문제인지 찾질못해서 이렇게라도 올려봅니다......

    다른사람들 풀이를 먼저 볼수 있긴한데 먼저 나만의 코드로 풀고싶어서 보진 않았습니다.

    혹시 보시고 해결해주실분 있나요 ????????????????????????????????????

    알고리즘 풀이전략 :
    n by n 행렬을 데리고 다니면서 첫째줄 , 둘째줄 ... n-1번째줄 에 1을 넣음 으로써
    마지막 n번째줄 행에서 '0'존재해서 1을넣을수 있다면 정답.
    이것을 이용해 정답을 알아본다.

    1.Queen 클래스와 클래스에 n by n 행렬을 만들고 0으로 채운다
    2.현재 라인(1~n)인 행에서 0인 곳을 찾아 1을 채우는 차일드 만듬
    3.라인 n 에서 0을 가진 차일드가 있다면 답.

    #include<iostream>
#include<windows.h>
using namespace std;

class Queen {
private:
    int n; //체스판크기
    int line;   // 현재 몇번째 줄을 테스트할것인가.
    int own_number;  //자기가 넣어야하는 라인에서 왼쪽에서 몇번째에 1을 넣을건지
    int ans = 0;     // 체스판에 규칙대로 놓아진다면 증가
public:
    Queen * parent = NULL; // 부모 노드
    Queen * child = NULL; // 자식노드
    int **data = new int*[this->n]; // n by n 행렬 만듬

    int get_ans() {     //ans 받아옴
        return this->ans;
    }
    void add_ans() {    //정답이면 ans증가
        this->ans += 1;
    }
    void set_own_number(int n) {    //몇번째에 넣어야하는지 정함
        this->own_number = n;
    }
    int get_own_number() {  //own_number 가져옴
        return this->own_number;
    }
    int addline() {         //자식노드에서 라인추가됨
        this->line = this->line + 1;
        return this->line;
    }
    int getn() {            //n을 얻음
        return this->n;
    }
    void setn(int n) {
        this->n = n;
    }
    void setline() {
        this->line = 0;
    }
    int getline() {
        return this->line;
    }
    int check_parent_line() {
        return this->parent->getline();
    }
    int* check_unoccupied_point_number() {  
        //현재 체크해야하는라인에서 비어잇는 곳의 인덱스를 행렬로 변환
        // ex) {1,2,4} <- 1,2,4번째에 다음노드에서 1을 넣어야함
        int n = this->getn();
        int j = 0;
        int* unoccupied_array = new int[n];
        for (int i; i < n; i++) {
            if (this->parent->data[this->check_parent_line()][i] == 0) {
                unoccupied_array[j] = i;
                j++;
            }               
        }
        return unoccupied_array;
    }
    int check_unoccupied_point_num() {
        //현재 라인에서 몇개나 비어있는가?
        int sum = 0;
        int n = this->getn();
        for (int i; i < n; i++) {
            if (this->parent->data[this->check_parent_line()][i] == 0)
                sum += 1;
        }
        return sum;
    }
    Queen(Queen* parent) {
        //child에 이용할려고 생성함
        if (this->parent != NULL) {
            this->parent = parent;
            this->line = parent->addline();
            this->data = parent->data;
            this->n = parent->getn();
        }
    }

    Queen(int n) {
        //초기 root 에 이용할려고 생성
        this->setn(n);
        this->setline();
        for (int i = 0; i < n; i++) {
            this->data[i] = new int[n];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                this->data[i][j] = 0;
            }
        }
    }

    void set_unavailable_spot(int l,int k) {
        //행렬에 1을 넣을시 그로인해 6방향의 값을 못넣게
        //하기 위해 전방향을 1로 채움
        int n = this->getn();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if ( k + j < n && 0 <= k + j) {
                    if (this->data[l][k + j] == 0)
                        this->data[l][k + j] = 1;
                }
                if (k - j < n && 0 <= k - j) {
                    if (this->data[l][k - j] == 0)
                        this->data[l][k - j] = 1;
                }
                if (l+i < n && 0 <= l+i) {
                    if (this->data[l + j][k] == 0)
                        this->data[l + j][k] = 1;
                }
                if (l + i < n && 0 <= l + i
                    && k + j < n && 0 <= k + j) {
                    if (this->data[l + j][k+j] == 0)
                        this->data[l + j][k+j] = 1;
                }
                if (l + i < n && 0 <= l + i
                    && k - j < n && 0 <= k - j) {
                    if (this->data[l + j][k - j] == 0)
                        this->data[l + j][k - j] = 1;
                }
                if (l - j < n && 0 <= l - j) {
                    if (this->data[l - j][k] == 0)
                        this->data[l - j][k] = 1;
                }
                if (l - j < n && 0 <= l - j
                    && k + j < n && 0 <= k + j) {
                    if (this->data[l - j][k+j] == 0)
                        this->data[l - j][k+j] = 1;
                }
                if (l - j < n && 0 <= l - j
                    && k - j < n && 0 <= k - j) {
                    if (this->data[l - j][k - j] == 0)
                        this->data[l - j][k - j] = 1;
                }

            }
        }
    }
    void make_child() {
        int* p = this->check_unoccupied_point_number();  
        //부모노드의 데이터을 불러옴
        for (int i = 0; i < this->check_unoccupied_point_num(); i++) {  
        // 비어잇는데이터만큼 반복
            if (this->line == this->getn()) {      //마지막 라인
                Queen *tmp = new Queen(this);
                while (tmp->parent != NULL) {
                    tmp = tmp->parent;
                }
                tmp->add_ans();
                break;
            }
            else {                              //마지막 라인 아닌곳
                Queen *tmp = new Queen(this);
                tmp->set_own_number(p[i]);
                tmp->data[tmp->parent->getline()][tmp->get_own_number()] = 1;
                this->set_unavailable_spot(tmp->parent->getline(), tmp->get_own_number());
                tmp->make_child(); //계속 차일드 생성
            }
        }
    }
};
int main() {
    Queen a(3);
    cout << a.get_ans() << endl;
}

    간단한 의견이라도 ....부탁드립니다.


    7년 전
4개의 댓글이 있습니다.
  • Corea
    Corea

    우선 make_child 함수를 부르는 곳이 없네요..


    7년 전 link
  • leesm
    leesm

    맞네요 그전부터 틀렷다는거네요 ㅠ
    그전에 틀린걸 찾아볼게요


    7년 전 link
  • thstkdgus35
    thstkdgus35

    채점환경이 윈도우가 아니므로 윈도우 헤더는 사용하시면 안됩니다.


    7년 전 link
  • astein
    astein

    set_unavailable_spot 함수 내의 내용들에도 오류가 좀 있네요.
    다시 한 번 천천히 확인해보세요 :)


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.