무식하게 풀기(Brute force) - 1. 보글 게임

리뷰 중인 책 ( 알고리즘 문제 해결전략 1권 )에선 무식하게 푸는 것은 '완전 탐색'이라 한다.

완전 탐색을 하는데 있어 책에서 소개하는 전략은 재귀 호출의 활용이다. 

 

 

재귀 호출 or 재귀 함수란?

 

자신이 수행할 작업을 유사한 형태로 여러 조각으로 쪼갠 뒤 그 중 한 조각을 실행하고, 나머지를 자기 자신을 호출해 실행하는 함수이다. 이 때 '더이상 쪼개지지 않는' 최소한 작업에 도달했을 때 사례를 기저 사례(base case)라고 한다.

 

필자는 재귀 호출을 이용한 문제 풀이는 기저 사례를 세우는 것이 핵심이라 생각한다.

---

예제 : 보글 문제 (난이도 下)

 

https://algospot.com/judge/problem/read/BOGGLE

위 문제를 '무식하게' 재귀 호출을 이용해 풀어보고자 한다.

 

문제의 분할

 

첫번째 조각을 찾는 것은 간단하다. 전체 칸에서 단어의 시작 위치만 반환하면 된다.

그 다음 조각은 위치에 인접한 8칸을 조사하면 된다.

이 때 슬라이싱을 통해 앞 글자 하나를 때고 찾으면 된다.

 

기저 사례

 

0. 시작 위치가 범위를 벗어나면 무조건 실패

1. 위치 (y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패

2. (1번 경우에 해당되지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공

//슬라이싱을 통해 단어를 하나씩 때고 있으므로 단어가 한 글자인 경우 마지막 case에 해당한다.

 

※ Clean Code TIP

입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하자.

반복적인 코드를 제거하는 데 큰 도움이 된다.

 

구현

 

bool inRange(int y, int x)
{
	return !(y >= 5 || y < 0 || x >= 5 || x < 0);
}

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

bool hasWord(int y, int x, const string &word)
{
	//base case 0
	if (!inRange(y, x)) return false;
	//base case 1
	if (board[y][x] != word[0]) return false;
	//base case 2
	if (word.size() == 1) return true;
	//인접한 8칸 검사
	for (int direction = 0; direction < 8; direction++)
	{
		int nextY = y + dy[direction], nextX = x + dx[direction];
		if (hasWord(nextY, nextX, word.substr(1))) return true;
	}
	return false;
}

 

시간 복잡도 분석

 

예를 들어 A로 가득찬 격자에서, 단어 AAAAB를 찾는다 하면 B 전까지는 탐색해야 한다.

탐색은 단어의 길이가 N에 대해 N-1 단계까지 진행된다.

따라사 시간 복잡도를 다음과 같이 표현할 수 있다.

 

8^n-1 = O (8^n)

 

위 알고리즘은 긴 단어를 찾는데 있어 비효율적이다.

제목 그대로 무식하게 푼 결과이다.

이를 개선한 것은 추후에 작성할 것이다.