백준 9202번 Boggle

Boggle 

시간 제한메모리 제한제출정답맞은 사람정답 비율

10 초

512 MB

3918

1051

548

24.184%

문제

상근이는 보드 게임 "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에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;
int w,b;
int maxScore,maxLength,maxIdx,cnt;
int found[300001];

vector <string> dic(300000);
char board[5][5];
int visited[4][4];
string temp = "";
int dx[8] = {1,0,0,-1,-1,1,1,-1};
int dy[8] = {0,1,-1,0,-1,1,-1,1};


void DFS (int word, int idx, int x,int y) {
    if(dic[word].length()==idx && found[word]==0){
            found[word] = 1;
            if(idx == 3 || idx == 4) maxScore += 1;
            else if(idx == 5) maxScore += 2;
            else if(idx == 6) maxScore += 3;
            else if(idx == 7) maxScore += 5;
            else if(idx == 8) maxScore += 11;
            if(idx>maxLength){
                maxLength = idx;
                maxIdx = word;
            }
        cnt++;
        }
        else{
            for(int k = 0 ; k < 8 ; k++){
                int next_x = x + dx[k];
                int next_y = y + dy[k];
     
                if(next_x >= 0 && next_x < 4 && next_y >= 0 && next_y < 4 && !visited[next_x][next_y] && board[next_x][next_y] == dic[word][idx]){
                    visited[next_x][next_y] = 1;
                    DFS(word,idx+1,next_x,next_y);
                    visited[next_x][next_y] = 0;
                }
            }
        }
        visited[x][y] = 0;

  
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> w;
    dic.resize(w);

    for(int i=0; i<w; i++) {
        cin >> dic[i];
  
    }
    sort(dic.begin(),dic.end());

    cin >> b;
    while(b--){
        //보드 만들기
        for(int i=0; i<4; i++){
            cin>>temp;
            for(int j=0; j<4; j++){
                board[i][j] = temp[j];
                
            }
        }
        //초기화
        memset(found,0,w * sizeof(int));

        maxScore = 0;
        maxLength = -1;
        maxIdx = 0;
        cnt = 0;
        //단어찾기
        for(int t = 0 ; t < w ; t++){
            for(int i = 0 ; i < 4 ; i++){
                for(int j = 0 ; j < 4 ; j++){
                    if(board[i][j]==dic[t][0] && found[t]==0) {
                        visited[i][j] = 1;
                        DFS(t,1,i,j);
                    }
                }
            }
            

        }
        cout << maxScore << " " << dic[maxIdx] << " " << cnt << "\n";

    }
    return 0;
}

순차적으로 코드를 풀이해보면 우선 가장먼저 단어사전을 만들어주었고, 가장 긴 단어가 여러개인 경우 사전순으로 앞서는 것을 출력하라고 했기 때문에 sort를 사용하여 정렬해주었다.

그후, 이중배열을 이용해 board를 만들어 주었고 board의 16칸(4X4)을 돌면서 모든 단어 사전과 비교를 해주었다.
게임 사전의 단어의 첫글자와 보드의 글자가 같은 경우 단어의 다음 글자가 해당 보드의 가로,세로,대각선에 존재하는지 DFS를 이용해 확인하였다.  이때 한 보드에서 여러번 같은 문자를 게임에 사용하면 안되므로 체크를 위해 visited배열을 만들어주었다.
또, '한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다'라는 조건을 만족시키기 위해 found라는 배열을 사용하여 이미 찾은 단어인지 확인해주었다.

이제 DFS함수에 대해 설명을 하면 맨처음 단어 사전에서 단어를 찾았는지 판별해준다. 조건은 단어사전의 단어의 길이와 현재 인덱스가 같으면서 동시에 찾은적이 없는 것. 조건을 충족한다면 단어 길이에 따라 점수를 조정해준다. 출력해야할 요소중에 가장 긴 단어도 포함이기 때문에 idx와 maxIdx를 비교하여 저장한다.

단어를 못찾은 경우 계속해서 가로, 세로, 대각선을 탐색하는데 다음에 이동할 board가 가장자리인지, 단어사전의 다음글자와 같은지 등을 비교하여 visited를 1로 변경하고 DFS를 호출해 재귀탐색한다. 탐색이 끝난 후에는 다음 단어 탐색을 위해 visited를 초기화 해준다.

알고리즘 시작하면서 처음으로 풀이에 성공한 플래티넘문제였다.... 머리가 터질거같아 시간날때마다 야금야금 풀어서 정확한풀이 시간은 모르지만 한자리에서 풀었으면 아마 최소 4시간은 걸렸을듯;;; 풀면서도 내 코드가 너무 헷갈려서 주석을 달아가며 풀었다 함께 스터디 중인 팀원의 풀이방법을 보니 트라이라는 자료구조를 사용하면 훨씬 간단하게 풀 수 있는 문제같으나 시간상의 관계로 해당 풀이는 다음에 도전해보는것으로 했다.