보글게임 - 완전 탐색

주어진 5x5 격자 위에 문자들이 있다. 최대 8방향으로 문자들을 연결해서 찾으려는 단어가 존재하는지 검사하라.

 

찾으려는 단어가 격자위에 존재하는지 검사하기 위해서는 완전 탐색 해야한다.

처음 시작 좌표 값과 단어를 입력으로 할 시에 격자 위에 존재하는지 검사하는 알고리즘을 구현.

 

각 문자마다 최대 8방향을 검사하기 때문에 격자가 커지면 커질수록 시간 복잡도는 기하급수적으로 상승하게 된다. (지수 복잡도)

 

완전 탐색을 재귀를 이용해서 구현했다.

 

char board[5][5] = {
	{'U', 'R', 'L', 'P', 'M'},
	{'X', 'P', 'R', 'E', 'T'},
	{'G', 'I', 'A', 'E', 'T'},
	{'X', 'T', 'N', 'Z', 'Y'},
	{'X', 'O', 'Q', 'R', 'S'}
};

int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};

bool InRange(int x, int y)
{
	return (x <= 4 && y <= 4) || (x >= 0 && y >= 0);
}

bool hasWord(int x, int y, string word)
{
	bool answer = false;

	if(!InRange(x, y)) return answer;
	
	if(board[x][y] != word[0]) return answer;

	if(word.size() == 1) return true;

	for(int direction = 0; direction < 8; ++direction)
	{
		int newX = x + dx[direction];
		int newY = y + dy[direction];

		if(hasWord(newX, newY, word.substr(1)))
			return true;
	}

	return answer;
}