assertion fail 질문드립니다

  • swg0110
    swg0110

    안녕하세요 제가 코딩을 하던중 shift연산이 필요한 부분이 있어서
    shift연산을 하는데 그런 코드가 들어간 경우마다 모두 assertion failed error가 발생합니다. 어디서 발생하는 건지 재연이 안되서 도저히 잡을 수가 없네요ㅠㅠ 도움을 주시면 감사하겠습니다!

    //
//  main.cpp
//  allergy
//
//  Created by wongeun on 2015. 10. 27..
//  Copyright © 2015년 wongeun. All rights reserved.
//

#include <iostream>
#include <string.h>

#define NAME_LEN_MAX    10
#define NOT_EXIST       -999

using namespace std;

char** _arrName;
int _frdCount;
int _foodCount;

long* _arrState;
long _compState;

int _curOptSolution;

int** _arrMinFoodCount;

void mallocArrays();
void freeArrays();
int findFrdIdx(char* name);
void readFoodState();
int countMinFood(int foodIdx, long curState);

int main(int argc, const char * argv[]) {
    int caseCount = 0;
    int caseIdx = 0;
    cin >> caseCount;

    while (caseIdx < caseCount) {
        cin >> _frdCount >> _foodCount;

        mallocArrays();

        for (int i = 0; i < _frdCount; i++) {
            cin >> _arrName[i];
        }

        readFoodState();

        _compState = (true << _frdCount) - 1;
        _curOptSolution = 0;

        int foodCount = countMinFood(0, 0);
        cout << foodCount << endl;

        freeArrays();

        caseIdx++;
    }
    return 0;
}

void mallocArrays() {
    _arrName = new char*[_frdCount];
    _arrState = new long[_foodCount];
    _arrMinFoodCount = new int*[_foodCount];

    for (int i = 0; i < _frdCount; i++) {
        _arrName[i] = new char[NAME_LEN_MAX];
    }

    for (int i = 0; i < _foodCount; i++) {
        _arrMinFoodCount[i] = new int[true << _frdCount];
    }

    memset(_arrState, 0, _foodCount * sizeof(long));
}

void freeArrays() {
    for (int i = 0; i < _frdCount; i++) {
        delete[] _arrName[i];
    }

    for (int i = 0; i < _foodCount; i++) {
        delete[] _arrMinFoodCount[i];
    }

    delete[] _arrMinFoodCount;
    delete[] _arrName;
    delete[] _arrState;
}

void readFoodState() {
    for (int i = 0; i < _foodCount; i++) {
        int curFrdCount = 0;
        cin >> curFrdCount;

        char* name = new char[NAME_LEN_MAX];

        for (int j = 0; j < curFrdCount; j++) {
            memset(name, '\0', NAME_LEN_MAX * sizeof(char));
            cin >> name;

            int idx = findFrdIdx(name);
            if (idx < 0)
                continue;

            _arrState[i] |= (true << idx);
        }

        delete[] name;
    }
}

int findFrdIdx(char* name) {
    for (int i = 0; i < _frdCount; i++) {
        for (int j = 0; j < NAME_LEN_MAX; j++) {
            if (name[j] != _arrName[i][j])
                break;
            else if (name[j] == '\0')
                return i;
        }
    }

    return -1;
}

int countMinFood(int foodIdx, long accumState) {
    if (accumState == _compState)
        return 0;
    else if (foodIdx == _foodCount)
        return NOT_EXIST;
    else if (_arrMinFoodCount[foodIdx][accumState] != 0)
        return _arrMinFoodCount[foodIdx][accumState];

    long curState = _arrState[foodIdx];

    long conState = accumState | curState;
    long unconState = accumState;

    int conCount = countMinFood(foodIdx + 1, conState) + 1;
    int unconCount = countMinFood(foodIdx + 1, unconState);

    int rstCount = 0;
    if (unconCount >= 0)
        rstCount = (conCount < unconCount)? conCount : unconCount;
    else {
        if (conCount >= 0)
            rstCount = conCount;
        else
            rstCount = NOT_EXIST;
    }

    _arrMinFoodCount[foodIdx][accumState] = rstCount;

    return rstCount;
}

    #include <iostream>
#include <string.h>

#define BOGGLE_SIZE         5
#define DIRECTION_MAX       4
#define WORD_SIZE_MAX       10

#define CHAR_BASE           'A'
#define CHAR_IDX_MAX        30

using namespace std;

int ARR_DIFF[4][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}};

int _wordCount;
char** _arrBoggle;
char** _arrWord;
int* _arrWordLen;

int** _arrPointState;
int** _arrWordStat;

void mallocArrays();
void freeArrays();
void fillWordStat();
bool isWordExist(int wordIdx);

int main() {
    int caseCount = 0;
    int caseIdx = 0;
    cin >> caseCount;

    _arrBoggle = new char*[BOGGLE_SIZE];

    for (int i = 0; i < BOGGLE_SIZE; i++) {
        _arrBoggle[i] = new char[BOGGLE_SIZE];
    }

    while (caseIdx < caseCount) {
        // read board
        for (int i = 0; i < BOGGLE_SIZE; i++) {
            cin >> _arrBoggle[i];
        }

        cin >> _wordCount;

        mallocArrays();

        // read word
        for (int i = 0; i < _wordCount; i++) {
            cin >> _arrWord[i];
            _arrWordLen[i] = (int)strlen(_arrWord[i]);
        }

        // word charactor 별, 단어 별 정리
        fillWordStat();

        // 결과 출력
        for (int i = 0; i < _wordCount; i++) {
            cout << _arrWord[i] << ' ';

            bool isExist = isWordExist(i);

            if (isExist)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }

        freeArrays();

        caseIdx++;
    }

    for (int i = 0; i < BOGGLE_SIZE; i++) {
        delete[] _arrBoggle[i];
    }

    delete[] _arrBoggle;

    return 0;
}

void mallocArrays() {
    _arrWord = new char*[_wordCount];
    _arrWordLen = new int[_wordCount];
    _arrWordStat = new int*[_wordCount];

    for (int i = 0; i < _wordCount; i++) {
        _arrWord[i] = new char[WORD_SIZE_MAX];
        _arrWordStat[i] = new int[CHAR_IDX_MAX];

        memset(_arrWordStat[i], 0, CHAR_IDX_MAX * sizeof(int));
    }

    _arrPointState = new int*[BOGGLE_SIZE];

    for (int i = 0; i < _wordCount; i++) {
        _arrPointState[i] = new int[BOGGLE_SIZE];
        memset(_arrPointState[i], 0, BOGGLE_SIZE * sizeof(int));
    }
}

void freeArrays() {
    for (int i = 0; i < BOGGLE_SIZE; i++) {
        delete[] _arrPointState[i];
    }

    for (int i = 0; i < _wordCount; i++) {
        delete[] _arrWord[i];
        delete[] _arrWordStat[i];
    }

    delete[] _arrPointState;
    delete[] _arrWordStat;
    delete[] _arrWord;
    delete[] _arrWordLen;
}

void fillWordStat() {
    for (int i = 0; i < _wordCount; i++) {
        int len = _arrWordLen[i];

        for (int j = 0; j < len; j++) {
            char c = _arrWord[i][j];
            int charIdx = c - CHAR_BASE;
            int tmp = (true << j);
            int stat = _arrWordStat[i][charIdx];
            _arrWordStat[i][charIdx] = stat | tmp;
        }
    }
}

bool isWordExist(int wordIdx) {
    int len = _arrWordLen[wordIdx];
    int compStat = (true << len) - 1;

    for (int i = 0; i < BOGGLE_SIZE * BOGGLE_SIZE; i++) {
        int row = i / BOGGLE_SIZE;
        int col = i % BOGGLE_SIZE;

        char c = _arrBoggle[row][col];
        int charIdx = c - CHAR_BASE;

        int curState = _arrWordStat[wordIdx][charIdx];
        int curAccum = 0;

        int prevSum = 0;
        int prevAccum = 0;

        for (int j = 0; j < DIRECTION_MAX; j++) {
            int prevRow = row + ARR_DIFF[j][0];
            int prevCol = col + ARR_DIFF[j][1];

            if ((prevRow < 0) ||
                (prevCol < 0) ||
                (prevCol >= BOGGLE_SIZE))
                continue;

            char prevChar = _arrBoggle[prevRow][prevCol];
            int prevCharIdx = prevChar - CHAR_BASE;

            prevSum |= _arrWordStat[wordIdx][prevCharIdx];
            prevAccum |= _arrPointState[prevRow][prevCol];
        }

        curAccum |= curState;
        curAccum |= prevAccum;
        curAccum &= (~(curState << 1));
        curAccum &= (~(curState >> 1));
        curAccum |= prevSum;

        if (curAccum == compStat)
            return true;
        else
            _arrPointState[row][col] = curAccum;
    }

    return false;
}

    8년 전
5개의 댓글이 있습니다.
  • Being
    Being

    https://algospot.com/wiki/read/%EC%9E%90%EC%A3%BC_%ED%95%98%EB%8A%94_%EC%8B%A4%EC%88%98_%EB%AA%A8%EC%9D%8C#toc_2


    8년 전 link
  • swg0110
    swg0110

    ?? shift연산결과는 전부 long으로 받게 되어있고, 혹시 몰라서 name을 입력받는 char배열 크기 증가시키고, long을 long long으로 변환시키고, 1LL로 바꾸고 해 봤는데 똑같이 나요. 그리고 음식 수 친구 수 전부 50이하라는 조건이 있어서 long범위 overflow할 일도 없어보이고요
    어디부분이 잘 못 됐다고 얘기하시는 건가요??


    8년 전 link
  • kcm1700
    kcm1700

    2^{50}짜리 new []는 못합니다. 메모리 사용량도 확인해주세요.


    8년 전 link
  • kcm1700
    kcm1700

    두 번째 코드는 어떤 문제에 대한 답안인지 적어주셔야 확인해볼 수 있습니다.


    8년 전 link
  • swg0110
    swg0110

    그럼 allergy는 풀이 방법이 뭔가요?ㅠㅠ 전체탐색해서 2^n 알고리즘 짰다니 시간 초과가 나서...
    두 번째 꺼는 boggle입니다


    8년 전 link

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