아마추어 팀블로그

알고리즘 문제ID BOGGLE C언어 풀이 : 재귀호출(시간초과) 본문

IT/IT 개발

알고리즘 문제ID BOGGLE C언어 풀이 : 재귀호출(시간초과)

탓치 2016. 1. 19. 23:47

알고리즘 공부를 시작했습니다. 도서는 프로그래밍 대회에서 배우는 알고리즘 문제해결전략이라는 책으로, 알고리즘 관련 스터디에서는 유명한 책인가 봅니다.


앞으로 문제를 풀고, 그 결과 소스를 공유하는 방식의 포스팅을 진행할 예정입니다. 알고리즘 문제는 ALGOSPOT, Codeforces, Baekjoon Online Judge 등의 알고리즘 사이트에 있는 걸 풀 예정입니다. 다만 문제를 붙여넣으면 저작권 문제가 생길 수 있으니 링크만 가져다 넣겠습니다. 문제가 필요하신 분들은 링크를 따라가 주세요.


저는 C언어 밖에 쓸 줄 몰라서 답안은 모두 C 코드로 진행될 겁니다. C++도 써봐야 되는데...


예상컨데, 멀지 않은 미래에 제가 과거에 작성했던 코드들을 보면 얼굴이 뜨거워질 겁니다. 하지만 이렇게 산출물이 하나라도 나와야 공부하는 맛이 날 것 같아서 부끄러움을 무릅쓰고 이런 방식을 택해보았습니다. 계속 진행할 수 있길...


첫 번째 문제는 알고리즘 문제해결전략 6장의 보글게임입니다. (알고스팟 문제링크) 책의 첫 예제네요. 책에서는 Brute Force(무식하게 풀기)를 언급하면서 보글게임을 일단 재귀함수로 풀어보라고 시킵니다. 사실 재귀 호출은 조금만 depth가 깊어져도 시간이 많이 소요되는 방식이죠. 그래서 알고스팟에서 아래 재귀함수 풀이 제출하면 시간초과가 뜹니다. 하지만 책에서 재귀함수 풀이 기법을 연습해 보라고 했으니 일단 시키는 대로 풀이를 해 보았습니다.



보글게임 C언어 풀이 (재귀호출  방식으로 인한 시간초과) (혹시 틀린 점 있으면 댓글로 알려주세요.)


#include 
#include 
#pragma warning(disable:4996)

int C; // Test Case
char pan[10][10];
int N; // Num of Strings
char str[20];
int len;

// 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
	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;
}

int i, j, c, n;
int main(void)
{
	scanf("%d", &C);
	for (c = 0; c < C; c++)
	{
		for (i = 0; i < 5; i++)
			scanf("%s", pan[i]);
		scanf("%d", &N);
		for (n = 0; n < N; n++)
		{
			scanf("%s", str);
			len = strlen(str);
			for (i = 0; i < 5; i++)
			{
				for (j = 0; j < 5; j++)
				{
					int ret = search(i, j, 0);
					if (ret == 1)
						goto FINISH;
				}
			}

		FINISH:
			if (i == 5 && j == 5)
				printf("%s %s\n", str, "NO");
			else
				printf("%s %s\n", str, "YES");
		}
	}

	return 0;
}



Comments