algospot BOGGLE

문제 링크입니다: https://algospot.com/judge/problem/read/BOGGLE

프로그램 자체는 잘 돌아가는데 아무래도 메모리 초과로 런타임 에러가 계속 뜨는 것 같습니다.

여태까지 프로그램을 작성하면서 메모리를 신경쓴 적이 없어서 그런지 어떻게 수정해야할지 고민이네요...

혹시 코드를 간략화 시킬 요소가 있다면 댓글로 알려주시면 감사하겠습니다!

(2018 1-21 00:48 해결완료)

우선 문자열을 동적할당하면 메모리가 많이 차지하는 것 같아 동적할당을 하지 않기로 했습니다.

이후에 기록을 초기화하는 부분을 memset으로 대체하였고 큐 또한 사용하지 않고 printf로 출력했습니다.

cout과 cin이 예상외로 상당히 많은 메모리를 차지했습니다.

따라서 printf와 scanf 그리고 puts로 대체하였고 재귀문에 매개변수로 받던 word를 

전역변수로 빼면서 매개변수로 안 받도록 하였습니다.

수정하는데 https://blog.naver.com/kgh9812/221109411157의 게시물을 많이 참고했습니다.(작성한 코드가 상당히 비슷했기 때문에 참고하기 쉬웠습니다)

[런타임 오류 났던 코드(이쁘지만 메모리를 상당히 차지하는 코드)]

/*

보글은 5*5 크기의 알파벳 격자인 게임판의 한 글자에서

시작해서 펜을 움직이면서 만나는 글자를 그 순서대로

나열하여 만들어지는 영어단어를 찾아내는 게임

 

펜은 상하좌우 혹은 대각선으로 인접한 칸으로 이동할 수 있으며

글자를 건너뛸 수는 없다. 지나간 글자를 다시 지나가는 것은 가능하지만

펜을 이동하지 않고 같은 글자를 여러번 사용은 불가능

 

보글 게임판과 알고 있는 단어들의 목록이 주어질 때,

보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하시오

*/

#include <iostream>

#include <queue>

using namespace std;

 

struct offsets

{

        int x, y;

};

 

offsets moveDir[8] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} }; //방향(학교과제로 작성한 Maze Class에서 가져왔다)

 

char board[5][5]; //5*5 Boggle

bool record[5][5][10]; //기록용(예시에 나와있는 단어의 길이가 10을 초과하지 않기 때문에 길이를 임의로 10이라고 정의)

 

void clearRecord(void) //기록 초기화

{

        for (int i = 0; i < 5; i++)

               for (int j = 0; j < 5; j++)

                       for (int k = 0; k < 10; k++)

                              record[i][j][k] = 0;

}

 

bool search(int y, int x, char *word, int idx)

{

        record[y][x][idx] = 1; //방문했다는 것을 기록

        //범위 안에 있는가

        if (x < 0 || y < 0 || x>4 || y>4)

               return false;

        //첫 글자와 동일하지 않으면 해당 문장이 아니다

        if (board[y][x] != word[idx])

               return false;

        //마지막 글자까지 동일하다면 참

        if (idx==strlen(word)-1)

               return true;

        for (int i = 0; i < 8; i++)

        {

if (y + diry[i] < 5 && x + dirx[i] < 5 && y + diry[i] >= 0 && x + dirx >= 0)

{

                   if (record[y + moveDir[i].y][x + moveDir[i].x][idx + 1]) //이미 방문했다면 또 다시 방문할 필요 없음

                           continue;

                   if (search(y + moveDir[i].y, x + moveDir[i].x, word, idx + 1)) //재귀 호출

                           return true;

}

        }

        return false;

}

 

int main(void)

{

        queue<pair<char *, bool>> q;

        int test_case, word_num;

        char **word;

 

        cin >> test_case;

        if (test_case < 0 || test_case>50)

               exit(-1);

        for (int i = 0; i < 5; i++)

               cin >> board[i];

 

        for (int i = 0; i < test_case; i++)

        {

               cin >> word_num;

               if (word_num < 0 || word_num>10)

                       exit(-1);

               word=new char*[word_num];

               for (int j = 0; j < word_num; j++)

                       word[j] = new char[10];

               for (int j = 0; j < word_num; j++)

               {

                       clearRecord();

                       cin >> word[j];

                       bool result = false;

                       for (int k = 0; k < 5; k++)

                       {

                              for (int l = 0; l < 5; l++)

                              {

                                      if (search(k, l, word[j], 0))

                                              result = true;

                                      if (result) //찾았다면 반복문 탈출

                                              break;

                              }

                              if (result)

                                      break;

                       }

                       if (result)

                              q.push(make_pair(word[j], true));

                       else

                              q.push(make_pair(word[j], false));

               }

        }

        cout << endl;

        while (!q.empty()) //결과 출력

        {

               pair<char *, bool> answer = q.front();

               q.pop();

 

               cout << answer.first << " ";

               if (answer.second)

                       cout << "YES" << endl;

               else

                       cout << "NO" << endl;

        }

        for (int i = 0; i < word_num; i++)

               delete[]word[i];

        delete[]word;

        return 0;

}

[런타임 에러가 안나고 4ms만에 작동한 코드]

/*

보글은 5*5 크기의 알파벳 격자인 게임판의 한 글자에서

시작해서 펜을 움직이면서 만나는 글자를 그 순서대로

나열하여 만들어지는 영어단어를 찾아내는 게임

 

펜은 상하좌우 혹은 대각선으로 인접한 칸으로 이동할 수 있으며

글자를 건너뛸 수는 없다. 지나간 글자를 다시 지나가는 것은 가능하지만

펜을 이동하지 않고 같은 글자를 여러번 사용은 불가능

 

보글 게임판과 알고 있는 단어들의 목록이 주어질 때,

보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하시오

*/

#include <iostream>

#include <cstring>

using namespace std;

 

struct offsets

{

        int x, y;

};

 

offsets moveDir[8] = { { -1, 0 },{ -1, 1 },{ 0, 1 },{ 1, 1 },{ 1, 0 },{ 1, -1 },{ 0, -1 },{ -1, -1 } }; //방향(학교과제로 작성한 Maze Class에서 가져왔다)

 

char word[11]; //전역변수로 뺐다

char board[5][5]; //5*5 Boggle

bool record[5][5][10]; //기록용(예시에 나와있는 단어의 길이가 10을 초과하지 않기 때문에 길이를 임의로 10이라고 정의)

 

bool search(int y, int x, int idx)

{

        record[y][x][idx] = 1; //방문했다는 것을 기록

        //첫 글자와 동일하지 않으면 해당 문장이 아니다

        if (board[y][x] != word[idx])

               return false;

        //마지막 글자까지 동일하다면 참

        if (idx==strlen(word)-1)

               return true;

        for (int i = 0; i < 8; i++)

        {

               if (y + moveDir[i].y < 5 && x + moveDir[i].x < 5 && y + moveDir[i].y >= 0 && x + moveDir[i].x >= 0)

               {

                       if (record[y + moveDir[i].y][x + moveDir[i].x][idx + 1])

                              continue;//이미 방문했다면 또 다시 방문할 필요 없음

                       if (search(y + moveDir[i].y, x + moveDir[i].x, idx + 1))

                              return true;//재귀 호출

               }

        }

        return false;

}

 

void answer(void)

{

        int  word_num;

 

        for (int i = 0; i < 5; i++)

               scanf("%s", board[i]);

 

        scanf("%d", &word_num);

        for (int j = 0; j < word_num; j++)

        {

               memset(record, 0, sizeof(record));

               scanf("%s", word);

               printf("%s ", word);

               bool result = false;

               for (int k = 0; k < 5; k++)

               {

                       for (int l = 0; l < 5; l++)

                       {

                              if (search(k, l, 0))

                                      result = true;

                              if (result)

                                      break;//찾았다면 반복문 탈출

                       }

                       if (result)

                              break;

               }

               if (result)

                       puts("YES");

               else

                       puts("NO");

        }

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        for (int i = 0; i < test_case; i++)

               answer();

        return 0;

}

이 문제 덕분에 정답 적중률 수직낙하...

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]