[백준/BOJ] 백준 9202번 : Boggle

www.acmicpc.net/problem/9202

9202번: Boggle

트라이 자료구조를 통해 단어 사전의 단어를 저장하였고, visited로 방문한 곳을 표시해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <set>
using namespace std;

int w;
int b;
vector<string> board(4);
int visited[4][4];
set<string> result;
set<string>::iterator it;
int dxdy[8][2] = { {0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };

struct node
{
	node* children[26];
	bool finish;
	string word;
};

node* Make_node()
{
	node* ret = new node();

	for (int i = 0; i < 26; i++)
		ret->children[i] = NULL;

	ret->finish = false;
	ret->word = "";

	return ret;
}

void Delete_node(node*& here)
{
	for (int i = 0; i < 26; i++)
		if (here->children[i] != NULL)
			Delete_node(here->children[i]);
	delete here;
}

void Insert_node(node*& here, string& input, int index)
{
	if (index == input.size())
	{
		here->finish = true;
		here->word = input; //해당 단어를 저장

		return;
	}

	if (here->children[input[index] - 'A'] != NULL)
		Insert_node(here->children[input[index] - 'A'], input, index + 1);

	else
	{
		here->children[input[index] - 'A'] = Make_node();
		Insert_node(here->children[input[index] - 'A'], input, index + 1);
	}
}

void Search(node*& n_here, pair<int, int> p_here)
{
	if (n_here->finish == true)
		result.insert(n_here->word);

	//해당 위치 방문 표시
	visited[p_here.first][p_here.second] = 1;

	for (int i = 0; i < 8; i++)
	{
		pair<int, int> p_there = make_pair(p_here.first + dxdy[i][0], p_here.second + dxdy[i][1]);

		if (p_there.first >= 0 && p_there.first < 4 && p_there.second >= 0 && p_there.second < 4 && visited[p_there.first][p_there.second] == 0 && n_here->children[board[p_there.first][p_there.second] - 'A'] != NULL)
		{
			Search(n_here->children[board[p_there.first][p_there.second] - 'A'], p_there);
		}
	}

	//해당 위치 방문 해제
	visited[p_here.first][p_here.second] = 0;

}



int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	node* root = Make_node();
	string input;

	cin >> w;

	//트라이에 단어 사전에 있는 단어를 저장한다
	for (int i = 0; i < w; i++)
	{
		cin >> input;

		Insert_node(root, input, 0);
	}

	cin >> b;

	for (int i = 0; i < b; i++)
	{
		board.clear();
		for (int j = 0; j < 4; j++)
		{
			cin >> input;
			board.push_back(input);
		}

		result.clear();
		for (int k = 0; k < 4; k++)
		{
			for (int l = 0; l < 4; l++)
			{
				//해당 위치 알파벳으로 시작하는 단어가 있을때
				if (root->children[board[k][l] - 'A'] != NULL)
				{
					Search(root->children[board[k][l] - 'A'], make_pair(k, l));
				}
			}
		}

		int result_score = 0;
		string result_word = "";
		int result_num = 0;

		for (it = result.begin(); it != result.end(); it++)
		{
			if ((*it).size() == 3 || (*it).size() == 4)
				result_score += 1;
			else if ((*it).size() == 5)
				result_score += 2;
			else if ((*it).size() == 6)
				result_score += 3;
			else if ((*it).size() == 7)
				result_score += 5;
			else if ((*it).size() == 8)
				result_score += 11;

			if ((*it).size() > result_word.size() || ((*it).size() == result_word.size() && (*it) < result_word))
				result_word = (*it);

			result_num++;
		}

		cout << result_score << " " << result_word << " " << result_num << "\n";
	}

	Delete_node(root);

	return 0;
}