[알고스팟][완전탐색] 보글 게임

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

알고스팟에 보글 게임이라는 문제가 있다.

하지만 해당 문제는 주어진 조건 때문에 완전탐색으로는 풀 수 없다.

하지만 지금은 완전 탐색의 공부를 목적으로 문제를 푸는 것이기 때문에

완전 탐색으로 문제를 접근하겠다.

- 소스코드

static char[][] map = new char[5][5];
	
static final int[] dx = {-1, -1, -1, 1, 1, 1, 0, 0};
static final int[] dy = {-1, 0, 1, -1, 0, 1, -1, 1};
//5 x 5 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환.
static boolean hasWord(int y, int x, String word){
	//1. 시작 위치가 범위 밖이면 무조건 실패
	if(!(y >= 0 && y < 5 && x >= 0 && x < 5)){
		return false;
	}
	//2. 첫 글자가 일치하지 않으면 실패
	if(map[y][x] != word.charAt(0)){
		return false;
	}
	//3. 단어가 일치하면서 원하는 단어가 한 글자인 경우 항상 성공
	if(word.length() == 1){
		return true;
	}
	//인접한 여덟 칸을 검사한다.
	for(int direction = 0; direction < 8; direction++){
		int nextY = y + dy[direction];
		int nextX = x + dx[direction];
		//word.substring(1)을 하면
		//첫 번째 index 0을 제외하고 [1...]을 계속해서 수행한다.
		if(hasWord(nextY, nextX, word.substring(1))){
			return true;
		}
	}
	
	return false;
}

- Category : Brute-Force(완전탐색)

- My Thiking : 문제를 푸는 데 혼란이 왔었던 부분은, 한 글자가 두 번 이상 사용될 수 있다는 조건이었다. 이 부분이 무엇을 의미하는지에 대해 몰랐는데, 생각해보니  그래프 탐색 알고리즘에서 메모이제이션으로 방문했던 부분인지 체킹하는 부분을 생략한다는 얘기인것 같았다. 나머지는 2차원 배열에서 이동하는 방식은 비슷했다. 두번째로 생각해야할 조건은 기저조건의 설정이였는데, 1. 범위체킹 2. 첫 글자가 일치하지 않으면 항상 실패 3. 단어가 일치하면서 단어 길이가 한 글자인 경우로 항상 성공 으로 조건을 설정한다.

 

- Logic : 이 코드는 텅 빈 답에서 시작해서 매 단계마다 하나의 원소를 추가하는 일을 반복하다가, 하나의 답을 만든 뒤에는 이전으로 돌아가 다른 원소를 추가하는 식으로 모든 답을 생성한다.

여기서 재귀함수를 사용한 이유는 만약 반복문을 사용한다면 m개의 갯수만큼 반복문이 늘어나기 때문에 코드가 길고 복잡해지는데다, 골라야할 원소의 수가 입력에 따라 달라질 수 있는 경우에는 사용할 수 없다는 문제가 있다.