[종만북 문제] 보글 게임 (문제 ID : BOGGLE, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 기본적으로 완전 탐색으로도, 예제로 주어진 케이스는 해결 가능하다. 하지만 제출하면 Timeout 이 발생한다.

2. Timeout 해결을 위해서는...

---

[종만북 문제] 보글 게임 (문제 ID : BOGGLE, 난이도 : 하)

기본적으로 완전 탐색으로 코드를 짜 보자. 무식하게 탐색한다면, 인접한 각 탐색 마다 인접한 8 개의 문자를 확인해야 하므로, 시간 복잡도는 O(8^N) 이 될 것이다.

#include <iostream>
#include "stdlib.h"
#include <vector>
#include <queue>

using namespace std;

char board[5][5];
int N;
vector<string> words;

int dir[8][2] = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };

struct target
{
	int row;
	int col;
	int idx;
};

struct cmp
{
	bool operator()(const target l, const target r) const
	{
		return l.idx < r.idx;
	}
};

bool findWord(const string& word)
{
	priority_queue<target, vector<target>, cmp> q;
	for (int i = 0; i < 5; ++i)
		for (int j = 0; j < 5; ++j)
			if (board[i][j] == word[0])
				q.push({ i, j, 0 });

	while (!q.empty())
	{
		target cur = q.top();
		q.pop();

		if (cur.idx == word.size() - 1)
			return true;

		for (int d = 0; d < 8; ++d)
		{
			int nRow = cur.row + dir[d][0];
			int nCol = cur.col + dir[d][1];

			if (nRow < 0 || nRow >= 5 || nCol < 0 || nCol >= 5)
				continue;

			if (board[nRow][nCol] == word[cur.idx + 1])
			{
				q.push({ nRow, nCol, cur.idx + 1 });
			}
		}
	}

	return false;
}

void sol()
{
	for (const string& word : words)
	{
		bool found = findWord(word);
		cout << word << " ";
		if (found) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

void inputHandler()
{
	for (int i = 0; i < 5; ++i)
	{
		string row;
		cin >> row;
		for (int j = 0; j < 5; ++j)
			board[i][j] = row[j];
	}

	cin >> N;
	words.resize(N);
	for (int i = 0; i < N; ++i)
		cin >> words[i];
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		// fill board & words
		inputHandler();

		sol();
	}
	
	return 0;
}

불행히도.. 위처럼 완전 탐색을 이용하면 Timeout 이 난다.

 

책에서 나온 코드는 다음과 같은데, 이 역시도 Timeout 이 날 것이다. 😅

 

그렇다면 Timeout 을 해결한 코드는...? 8 장에서 DP 를 이용하게 되는데, 그 때 공개하도록 하겠다. 😉