[C++] 백준 9202번 : Boggle

문제

 

상근이는 보드 게임 "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 <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector <string> dic;
 
char board[5][5];
int visited[5][5];
 
int dx[8] = {1,0,0,-1,-1,1,1,-1};
int dy[8] = {0,1,-1,0,-1,1,-1,1};
 
int found[300005];
int max_score;
int max_len;
int max_idx;
int word_cnt;
 
void DFS(int word, int idx, int cur_x,int cur_y){
    if(dic[word].length()==idx && found[word]==0){
        found[word] = 1;
        if(idx == 3 || idx == 4) max_score += 1;
        else if(idx == 5) max_score += 2;
        else if(idx == 6) max_score += 3;
        else if(idx == 7) max_score += 5;
        else if(idx == 8) max_score += 11;
        if(idx>max_len){
            max_len = idx;
            max_idx = word;
        }
        word_cnt++;
    }
    else{
        for(int k = 0 ; k < 8 ; k++){
            int next_x = cur_x + dx[k];
            int next_y = cur_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[cur_x][cur_y] = 0;
}
 
int main(){
    int w;
    scanf("%d",&w);
 
    string tmp = "";
    getline(cin,tmp);
    for(int i = 0 ; i < w ; i++){
        getline(cin,tmp);
        dic.push_back(tmp);
    }
 
    sort(dic.begin(), dic.end());
    getline(cin,tmp);
 
    int b;
    scanf("%d",&b);
 
    while(b--){
        getline(cin,tmp);
        for(int i = 0 ; i < 4 ; i++){
            getline(cin,tmp);
            for(int j = 0 ; j < 4 ; j++) board[i][j] = tmp[j];
        } // make board
 
        // initialize
        for(int i = 0 ; i < w ; i++) found[i] = 0;
        max_score = 0;
        max_len = -1;
        max_idx = 0;
        word_cnt = 0;
 
        // find word
        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);
                    }
                }
            }
        }
 
        // output
        cout << max_score << " " << dic[max_idx] << " " << word_cnt << "\n";
    }
}

 

먼저 getline 함수를 문자열을 읽어 게임 사전을 만들어주었습니다. 게임 사전은 string형의 vector를 사용하였습니다.

가장 긴 단어가 여러개인 경우 사전순으로 앞서는 것을 출력하라는 조건을 맞추기 위해 sort를 이용하여 게임 사전을 정렬해주었습니다. 기존의 길이가 가장 긴 단어의 길이와 같은 경우는 갱신하지 않게 작성한다면 가장 긴 단어가 여러개인 경우 사전순으로 앞서는 것을 출력할 수 있습니다.

 

그 후 board를 기준으로 답을 출력해주었습니다. 게임 사전을 만들 때와 같이 getline 함수를 이용하여 char 이중배열 형식의 보드를 만들어 주었습니다. 그 후 문제를 해결하기 위해 쓰일 변수들을 초기화 시켜 주었습니다. 한 문자열을 여러번 찾는 경우에도 한번으로 취급하기 때문에 이미 찾았던 문자열은 배열에 체크를 해주고 더이상 확인을 하지 않기 위해 found 배열을 만들어주었습니다. 

 

board의 16칸을 반복문으로 돌면서 모든 게임 사전의 경우를 확인해주었습니다. 게임 사전의 단어의 첫글자와 보드의 글자가 같은 경우 단어의 다음 글자가 보드의 가로,세로,대각선에 존재하는지 확인하기 위해 DFS 함수를 이용해주었습니다. 이 때 vector의 몇번째 단어인지와 index, 보드에서의 위치를 인자로 가지고 함수에 들어가게 하였습니다. 또한 한 보드에서 여러번 같은 문자를 게임에 사용하면 안되므로 체크를 위한 visited 배열도 만들어주었습니다.

 

DFS 함수 내에서는 게임 사전의 단어가 보드에 존재한다면 점수에 더해주고 찾은 단어의 개수와 가장 길이가 긴 단어에 대한 값들을 갱신시켰습니다. 아직 단어가 보드에 존재하는지 찾고있다면 보드 범위 내에서 visited 배열에 체크를 한 후 DFS 함수를 재귀적으로 불러 탐색합니다. 이 때 주의해주어야 할 점은 DFS 함수에서 나올 때 방문을 체크한 visited를 다시 0으로 바꾸어주어야 모든 경우를 찾을 수 있습니다.