기술면접 알고리즘 [Graph] : Boggle (Array Board 에서 단어 찾기)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

Boggle : Find all possible words in a board of characters

다음과 같은 보드가 있다고 가정했을때, Dictionary에서 우리가 원하는 단어를 보드를 통해 만들 수 있는지 없는지 확인하는 코드를 짜 보자.

인풋과 아웃풋은 다음과 같다.

제약 조건은, 보드에서 상하좌우 + 대각선 총 8가지 방향으로 이동할 수 있다는 것과, 보드 위의 문자를 중복해서 방문하는 것은 안된다는 것이다. 해당 함수는 DFS 방식으로 구현해야 한다.

#include <cstring>
#include <iostream>

#define M 3
#define N 3

std::string dictionary[] = { "GEEKS", "FOR", "QUIZ", "GO" };
int n = sizeof(dictionary) / sizeof(dictionary[0]);

bool isWord(std::string& str) {
	for (int i = 0; i < n; ++i) {
		if (str.compare(dictionary[i]) == 0)
			return true;
	}
	return false;
}

// A recursive function to print all words present on boggle
void findWordsUtil(char boggle[M][N], bool visited[M][N], int i, int j, std::string str) {

	visited[i][j] = true;
	str = str + boggle[i][j];

	if (isWord(str)) {
		std::cout << str << std::endl;
		return;
	}

	// Traverse 8 adjacent cells
	for (int row = i - 1; row <= i + 1 && row < M; ++row)
		for (int col = j - 1; col <= j + 1 && col < N; ++col)
			if (row >= 0 && col >= 0 && !visited[row][col])
				findWordsUtil(boggle, visited, row, col, str);


	// Erase current character from string and mark visited
	// of current cell as false
	str.erase(str.length() - 1);
	visited[i][j] = false;
}

// Prints all words present in dictionary
void findWords(char boggle[M][N]) {
	bool visited[M][N] = { { false } };

	std::string str = "";

	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N; ++j)
			findWordsUtil(boggle, visited, i, j, str);
}

int main() {
    char boggle[M][N] = { { 'G', 'I', 'Z' },
                          { 'U', 'E', 'K' },
                          { 'Q', 'S', 'E' } };
 
    std::cout << "Following words of dictionary are present\n";


    findWords(boggle);



    return 0;
}