아마추어 팀블로그

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

IT/IT 개발

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

탓치 2016. 1. 23. 09:30

지난 보글(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


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



Comments