알고스팟 Boggle 문제

군대에 있는 내 친구는 시간날때마다 알고리즘 문제같은걸 몇 가지 알려주곤 한다. 학기중에는 이리저리 바빠서 안 보고, 학기가 끝나서는 귀찮아서 안 보는 중이었는데 끈질기게도 휴가나와서 이런 문제가 있다고 알려주더라.

문제 내용 : https://algospot.com/judge/problem/read/BOGGLE

그림1. 왠지 그냥 허전해서 링크에 있는 이미지를 가져왔다.

개인적으로 알고리즘 문제를 그리 많이 풀어보진 않았지만, 대부분의 문제들은 문제를 읽어보면서 생각나는 가장 간단한 방법의 로직으로 풀려고 하면 대부분 시간 초과에 걸리는 경우가 많았던것 같다. (사실 가장 직관적인 방법으로 풀 수 있으면 아마도 어려운 문제가 아니겠지) 이 문제를 처음 읽으면서, '첫번째 글자를 찾고, 그 주위 8방위로 재귀함수 돌리면서 문자 하나씩 확인하면 될거 같기도 한데' 라고 생각했지만 아예 대놓고 '6장의 예제 코드는 이 문제를 풀기에는 너무 느립니다. 6장의 뒷부분과 8장을 참조하세요.' 라고 쓰여져 있기도 하고 (6장이 뭔진 모르지만), 밑에 댓글을 보니 나 처럼 풀려다가 실패한 사람들이 어떤 경우에 실패하는지 테스트 케이스도 몇개 올려 놓기도 한걸 보고 그 생각은 잊기로 했다. 사실 생각해보니 그 친구도 시간초과 떴다고 했었던거 같았다.

아래쪽 댓글에 적혀있기도 하지만 문제의 분류를 눌러보니 동적계획법을 쓰라고 나온다. 동적계획법이라는 단어에 익숙하지 않아서 뭔지 좀 생각을 해보니 알고리즘 수업시간에 배운 Dynamic Programming이 생각났다. 수업시간에 교수님이 Programming 이라는 단어가 코드짜는 프로그래밍이 아니라 Planning에 가깝다고 말한것도 생각났다. 동적 계획법이 무엇인지 설명하기 위해 당시 수업 들으며 필기한것을 인용하자면 '배열에다가 계산결과를 저장해놔서 나중에 다시 계산 안 하고 써먹는 것' 이라고 할 수 있겠다. 물론 이런저런 자세한 설명은 다 잘라 먹었지만.

위키피디아를 링크해 주는게 전체적인 글의 질을 향상시켜 주겠지만 그래도 잘라먹은 설명을 좀 더 하자면, 동적계획법은 마치 점화식처럼 이전 값을 이용해서 다음 값을 계산할 수 있을때 사용할 수 있다. 가장 만만한 피보나치 수열(다른 만만한 녀석으로는 팩토리얼이 있다.)로 예를 들어보면, 피보나치 함수를 f(n)이라고 할때 5번째 항의 값인 f(5)를 구하려면 f(4)와 f(3)을 구해서 더해야 한다. f(4)와 f(3)을 또 각각 구하려면 f(3), f(2) 더 들어가면 f(1)까지 필요하고. 이때 이전 항의 값들을 테이블(배열)에 담아두고 있다가 필요할때 재 계산 하는게 아니라 계산해 둔걸 빠르게 가져다 쓰는게 동적계획법이다.

동적계획법으로 문제를 풀기 전에, 왜 재귀방법으로(8방향으로 검사하는거) 풀면 느려터져서 시간 초과가 걸리는거냐 하면 '중간에 여러 갈래로 나아가는 경우가 생기기 때문'이다. 위에 그냥 추가한 그림1.(c)를 보면 "GIRL"이라는 단어를 검사하고 있는데 이건 앞서 말한 재귀방법으로 풀어도 별 문제 없다. 그냥 G부터 찾고 오른쪽에서 I 찾고 그 오른쪽 위에서 R찾고 마지막으로 위에서 L 찾으면 되니까. 문제는 그림1.(b)처럼 중간에 갈 수 있는 길이 2가지 이상 생기는 경우가 있을 수 있다는것이다. (b)는 "PRETTY"를 찾고 있다. "PRE" 까지는 일단 찾았다고 치자 (그림 a는 신경쓰지 말고 일단), 이제 T를 찾아야 하는데 E 주변을 보면 T가 2개나 있다. 오른쪽 위와, 그냥 오른쪽. 만약 오른쪽 위로 올라간다면 정답을 찾을 수 있지만 그냥 오른쪽으로 가면 정답을 찾을 수 없다. 그렇다, 정답이 되는 경우와 안 되는 경우가 있기 때문에 가능한 후보들은 전부 뒤져봐야 이게 있는지 없는지 알 수 있단 말이다. 여기에서 시간을 까먹는 경우가 생긴다. 댓글을 인용하자면

NNNNN
NEEEN
NEYEN
NEEEN
NSNNN

위 판에서 YES를 찾는 입력을 만들어 넣어보세요.

이런 경우, "YE"까지 찾아놓고 마지막 'S'를 찾기위해 신나게 돌아다니다 시간 다 끝난다는거다.

그러면 이 문제에 대한 점화식을 어떻게 세우고, 어떻게 동적계획법으로 풀까. 사실 여기까지 읽은 사람이 있다면 약간 배신감을 느낄 수도 있겠지만 나는 교과서에 나올법한 깔끔한 동적 계획법으로 풀어제낀게 아니라 '배열에 이전 값을 인용해서 다음값을 써넣는다' 라는 방법만 따와서 나름의 꼼수로 풀었다. 정공법으로 풀자면 단어 역순으로 어찌저찌 하면 될거 같은데 그러긴 귀찮고 별로 생각하기 싫던 와중에 야매 방식이 생각나서 그랬다.

아무튼 나만의 야매 방식을 설명 하자면, 값을 담는 테이블은 문제와 마찬가지로 5x5 배열로 한다. 알파벳 하나하나에 대해 값을 정하는데 초기값은 전부 0이다. 검사할 문자열 'word'에서 for문을 돌면서 캐릭터 'c' 를 하나씩 가져와서 값을 갱신하는데,

• 지금 검사하고 있는 'c'와 알파벳 배열(board)에서 현재 보고 있는 board[i][j]가 같으면 테이블에 1점을 추가한다.
• 추가하는데, 인접해 있는 8방에 점수가 있는놈(전에 'c'를 알파벳 배열과 검사할때 점수가 오른놈)이 있으면 주변 점수중에 제일 높은 점수에 1을 더한값을 매긴다.
• 다만, 최고 점수는 지금까지 검사한 'c'의 갯수를 넘기지 않는다.

라고 정리해 놓으면 이해하기 어려우니 그냥 코드를 보는게 나을지도 모르겠다.

int inline getNearMax(const int5x5& table, int i, int j){
	int max = 0;

	for(int k = -1; k < 2; k++)
	{
		for(int l = -1; l < 2; l++)
		{
			if(k == 0 && l == 0)
				continue;

			int val = safeAccess(table, i + k, j + l);
			max = max < val ? val : max ;
		}
	}

	return max;
}

bool bogglePossible(const char5x5& board, const std::string& word){

	int5x5 table= {0,};

	int len = word.length();
	for(int n = 0; n < len; n++){
		char c = word[n];

		int5x5 newTable = table;

		for(int i = 0; i < 5; i++)
		{
			for(int j = 0; j < 5; j++)
			{
				if(board[i][j] == c)
				{
					newTable[i][j] = min(getNearMax(table, i, j) + 1, n + 1);
				}
			}
		}

		table = newTable;
	}

	for(int i = 0; i < 5; i++)
	{
		for(int j = 0; j < 5; j++)
		{
			if(table[i][j] >= len) 
				return true;
		}
	}

	return false;
}

소스가 안보이면 gist를 참조하시라. (사실 'bogglePossible'에서 아래의 2중 for문은 위쪽 for문이랑 병합 시킬 수 있지만 그 전에 정답 판정 받았으니 그냥 냅두고 있다.)

이렇게 하면 아까 분기점이 생겼던 그림1.(b)의 상황에서 P,R,E가 각각 1,2,3점을 얻었으니 '오른쪽 위' T와  '그냥 오른쪽' T는 똑같이 4점을 받게 된다. 그 이후가 다른점인데 "PRET"까지 본 상황에서 다음으로 검사할 문자는 다시 'T' 이다. 4점이었던 T들은 이번 루프에서 서로가 인접해 있으니 각각 5점으로 오른다. 마지막으로 'Y'를 검사할때, 5점을 받았던 T와 인접해 있으니 6점을 받고 루프가 끝난다. 그리고 아래에 있는 최적화 안 시켜 놓은 2중 for문에 의해 return true;하게 된다.

테이블 안에 있는 변수, 그러니까 점수의 의미를 게임에서의 MAX콤보처럼 이해하면 쉬우려나 모르겠다. 아무튼 더 좋은 많은 방식들도 많이 있겠지만 나는 이런 방식으로 풀었다. 아래는 전체 코드이고 아까도 언급한 것처럼 gist링크도 걸어놨다. 끝.