좌표계에서 인접한 좌표들을 순차적으로 참조하는 C함수의 개선

지난 보글(Boggle) 알고리즘 문제 풀이에 작성했던 search() 함수는 현재 좌표 (x, y)의 인접한 8개의 좌표들에 대해 각각 search() 함수를 호출하는 재귀 호출 방식을 띠고 있습니다. (문제 풀이 링크: 알고리즘 문제ID BOGGLE C언어 풀이 : 재귀호출(시간초과))

search() 함수만 가져오면 아래와 같습니다.

int search(int ii, int jj, int idx)
{
	if (ii < 0 || ii >= 5 || jj < 0 || jj >= 5) return 0;
	if (idx >= len) return 0;
	if (pan[ii][jj] != str[idx]) return 0;

	// Done!
	if (pan[ii][jj] == str[idx] && idx == len - 1) return 1;

	// Recursive Call
	if (search(ii - 1, jj - 1, idx + 1)) return 1;
	if (search(ii, jj - 1, idx + 1)) return 1;
	if (search(ii + 1, jj - 1, idx + 1)) return 1;
	if (search(ii + 1, jj, idx + 1)) return 1;
	if (search(ii + 1, jj + 1, idx + 1)) return 1;
	if (search(ii, jj + 1, idx + 1)) return 1;
	if (search(ii - 1, jj + 1, idx + 1)) return 1;
	if (search(ii - 1, jj, idx + 1)) return 1;

	// Can't find
	return 0;
}

빨간색으로 처리한 부분을 보면 search() 함수를 인자만 -1, 0, +1 등으로 변경하여 총 8회 호출하고 있습니다. 이러한 반복호출 작성 시, 함수 인자를 작성할 때 실수하기가 정말 쉽습니다. 그래서 아래와 같이 함수를 수정하면 틀릴 위험이 줄어듭니다.

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

// Found: 1, Not Found: 0 Return
int search(int ii, int jj, int idx)
{
	if (ii < 0 || ii >= 5 || jj < 0 || jj >= 5) return 0;
	if (idx >= len) return 0;
	if (pan[ii][jj] != str[idx]) return 0;

	// Done!
	if (pan[ii][jj] == str[idx] && idx == len - 1) return 1;

	// Recursive Call
	int dir = 0;
	for (dir = 0; dir < 8; dir++)
		if (search(ii + dx[dir], jj + dy[dir], idx + 1))
			return 1;

	// Can't find
	return 0;
}

수정한 부분은 Bold 처리 했습니다. 8번 search() 함수를 호출하던 것이, for문을 8 loop 돌리는 것으로 대체되었습니다. const int형 배열인 dx[8]와 dy[8]는 현재 좌표인 (x, y) 주변 좌표들의 상대 위치를 나타냅니다. 예를 들어 현재 좌표 (x, y)의 좌상단 좌표는 (x - 1, y - 1)이며, 이를 표현하기 위해 dx[0], dy[0]은 각각 -1, -1 값을 가집니다. 아래 표를 참고하시면 제가 정의한 dx와 dy 배열은 좌상단으로부터 시계 방향으로 돌렸을 때 얻어낼 수 있음을 알 수 있습니다.

x - 1, y - 1	x, y - 1	x + 1, y - 1
x - 1, y	x, y	x + 1, y
x - 1, y + 1	x, y + 1	x + 1, y + 1

괜히 숫자 하나 기입을 잘못해서 디버깅 시간을 잡아먹는 경우가 종종 있습니다. 실수할 가능성을 최대한 줄이는 것이 좋을 것 같네요.