[BOJ 백준] Boggle(9202) C++

 

링크 : https://www.acmicpc.net/problem/1991

 

문제 설명 : 

상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 

상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.

Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.

1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.

단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.

그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나  있다.

출력 : 

각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

 

예제 입력 : 

5
ICPC
ACM
CONTEST
GCPC
PROGRAMM

3
ACMA
APCA
TOGI
NEST

PCMM
RXAI
ORCN
GPCG

ICPC
GCPC
ICPC
GCPC

예제 출력 : 

8 CONTEST 4
14 PROGRAMM 4
2 GCPC 2

 

 

접근법 : 

1) 어떻게 풀 것인가?

Trie 구조 활용

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// boggle 9202 C++
#if 1
#include <iostream>
#include <string>
using namespace std;

struct Trienode {
    Trienode* child[26] = { NULL, };
    bool isEnd = false;
    bool ishit = false;
};

int dx[8] = { -1, -1, -1, 0, 0, 1, 1 , 1 };
int dy[8] = { -1, 0, 1, -1, 1, -1, 0 , 1 };

int scoring[9] = { 0,0,0,1,1,2,3,5,11 };
Trienode* root;
int w, b;
char map[4][4];
bool visit[4][4];
int word_count, score;
void insert(string);
bool iscontained(string);
void DFS(int, int, Trienode*, int);
void clear(string);

string answ;
string foundword;

int main() {

    root = new Trienode;
    cin >> w;

    string* words = new string[w];

    for (int i = 0; i < w; i++) {
        cin >> words[i];
        insert(words[i]);
    }

    cin >> b;
    // boggle board 탐색.
    for (int i = 0; i < b; i++) {

        answ = "";
        foundword = "";

        score = 0;
        word_count = 0;

        //ishit, isend 초기화.

        //boggle map 입력 받음.
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                cin >> map[j][k];
                visit[j][k] = false;
            }
        }

        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                if (root->child[map[j][k] - 'A'] != NULL) {

                    foundword = "";
                    DFS(j, k, root->child[map[j][k] - 'A'], 1);
                }
                //시작점을 다르게 해서. 
            }

        }
        cout << score << " " << answ << " " << word_count << "\n";

        //clear ishit
        for (int i = 0; i < w; i++) {
            clear(words[i]);
        }
    }

}

void clear(string s) {

    Trienode* cur = root;
    for (int i = 0; i < s.size(); i++) {
        cur = cur->child[s.at(i) - 'A'];
    }

    cur->ishit = false;
}

void DFS(int r, int c, Trienode* cur, int count) {

    // 1. 체크인.
    visit[r][c] = true;

    //만들어진 문자열에 추가하기.
    char word = map[r][c];
    foundword += map[r][c];

    // 존재하지 않는 단어면 keep going.
    // 있고 만약 isend도 참이라면 단어 맞음 !, 근데 찾은 단어는 포함시키면 안됨.
    if (cur->isEnd == true && cur->ishit == false)
    {
        cur->ishit = true;
        word_count++;
        score += scoring[count];

        if (answ.size() < foundword.size()) answ = foundword;
        else if (answ.size() == foundword.size()) {
            if (foundword.compare(answ) < 0) {
                answ = foundword;
            }
        }
    }

    // 5. 갈 수 있는 곳 선택 ( 8방향 )
    for (int i = 0; i < 8; i++) {
        int temp_r = r + dx[i];
        int temp_c = c + dy[i];

        // 6. 방문한 곳인지 확인. 
        if (0 <= temp_r && temp_r <= 3 && 0 <= temp_c && temp_c <= 3)
        {
            if (visit[temp_r][temp_c] == false) {
                //7. 간다.
                if (cur->child[map[temp_r][temp_c] - 'A'] != NULL) { //haschild 
                    DFS(temp_r, temp_c, cur->child[map[temp_r][temp_c] - 'A'], count + 1);
                }
            }
        }

    }
    // 8. 체크아웃. 
    visit[r][c] = false;
    foundword.erase(foundword.length() - 1);
    // 만든 문자열 마지막꺼 빼기. 체크아웃
        }

void insert(string word) {

    Trienode* current = root;
    for (int i = 0; i < word.size(); i++) {

        int idx = word[i] - 'A';

        if (current->child[idx] == NULL) {
            current->child[idx] = new Trienode;
        }
        current = current->child[idx];

    }
    current->isEnd = true;

}

bool iscontained(string word) {

    Trienode* current = root;

    for (int i = 0; i < word.size(); i++) {

        int idx = word[i] - 'A';

        if (current->child[idx] == NULL) {
            return false;
        }

        current = current->child[idx];
    }

    return current->isEnd;
}
#endif