Boggle game

dlsghl92·2019년 10월 11일
0

알고리즘

목록 보기
1/1

(출처) https://algospot.com/judge/problem/read/BOGGLE

본 문제는 완전탐색으로 풀려면 대략 25 * (8^n) 개의 경우의 수를 전부 확인해야하고, 그에따라 해당 횟수만큼 반복문을 수행해야한다. (n은 주어진 단어의 길이 - PRETTY, GIRL, REPEAT)

최악의 경우 25 * 10억의 경우의 수를 검색하기때문에 당연히 시간초과가 예상된다. 따라서 메모이제이션을 이용해 중복되는 경우를 지워주기로 했다.

생각한 로직은 5x5 맵에 존재하는 총 25개의 좌표들 각각마다 방문순서에 따른 성공여부를 저장하는 메모이제이션 배열을 생성하는 것이었다.

위 문제 예시로 주어진 그림(a)의 맵과 GIRL라는 단어로 예를 들어보면,

단어 GIRL의 문자열 길이는 4개이기 때문에 그림(a)에서는 총 4번의 움직임이 일어난다. 4번의 움직임으로 'G'-'I'-'R'-'L' 방문순서를 만족하는 경우를 찾으면서 (dp[G][0] = dp[I][1] = dp[R][2] = dp[L][3] = 성공 ) 도중에 일어나는 실패는 저장하여 중복을 피한다.

DP[x좌표,y좌표][방문한 순서] 의 성공여부

=

for (int i = 0; i < 8개의 이동좌표; i++)
{ DP[x(i) 좌표, y(i) 좌표] [방문한 순서 + 1] 의 성공여부 (8개의 경우 중 하나라도 성공하면 성공) }

기저사례 : 주어진 단어의 마지막 문자에 해당하는 방문순서일 때

코드

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <string>


using namespace std;



vector<int> dx = { 1,1,1,-1,-1,-1,0,0 };
vector<int> dy = { 0,1,-1,0,1,-1,1,-1 };


int hasWord(vector<vector<int>>& dp, string word, vector<string> &map, int n, int xy)
{
	int obj = 0;
	int x = xy % 5;
	int y = xy / 5;

	int &ret = dp[xy][n];
	
	if (ret != -1) return ret;

	if (map[y][x] != word[n]) return ret = 0;

	if (n == 0) return ret = 1;

	for (int i = 0; i < dx.size(); i++)
	{
		x += dx[i];
		y += dy[i];

		if (x < 0 | x > 4 | y < 0 | y > 4)
		{
			x -= dx[i];
			y -= dy[i];
			continue;
		}

		xy = x + (y * 5);
		obj = hasWord(dp, word, map, n - 1, xy);
		x -= dx[i];
		y -= dy[i];

		if (obj == 1) break;

	}

	return ret = obj;
}

int main()
{
	int testcase;
	scanf("%d", &testcase);
	getchar();


	for (int j = 0; j < testcase; j++)
	{
		vector<string> map = { "00000","00000", "00000", "00000", "00000" };

		for (int i = 0; i < 5; i++)
		{
			getline(cin, map[i]);
		}

		int wordN;
		scanf("%d", &wordN);
		getchar();
		vector<string> word;

		for (int i = 0; i < wordN; i++)
		{
			string keyword;
			getline(cin, keyword);
			word.push_back(keyword);
		}

		//메인 로직
		for (int i = 0; i < word.size(); i++)
		{
			int obj = -1;
			vector<vector<int>> dp(25, vector<int>(10,-1));

			for (int xy = 0; xy < 25; xy++)
			{
				obj = hasWord(dp, word[i], map, word[i].length() - 1, xy);
				if (obj == 1) break;
			}
				
			if (obj == 1) cout << word[i] << " YES\n";
			else cout << word[i] << " NO\n";

		}
		
	}
	
	return 0;
}
profile
안녕하세요. 잘부탁드립니다.

0개의 댓글