완전탐색 - 보글 게임 (난이도 : 하, Java)

문제와 내용은 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략" 책을 참고하였습니다.

알고리즘 문제 해결 전략

 

---

 

이것을 풀기 위한 가장 간단한 방법은 완전 탐색을 이용해, 단어를 찾아낼 때까지 모든 인접한 칸을 하나씩 시도해 보는 것이다. 그중 한 칸에서라도 단어를 찾을 수 있으면 성공이고, 어느 칸을 선택하더라도 답이 없다면 실패가 된다.

 

문제의 분할

hasWord()가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다. 함수 호출 시에 단어의 시작 위치를 정해주기 때문에, 문제의 조각들 중 첫 번째 글자에 해당하는 조각을 간단하게 해결할 수 있다. 시작 위치에 쓰여 있는 글자가 단어의 첫 글자와 다르다면 곧장 false를 반환하고 종료하면 되기 때문이다. 그러고 나면 원래 단어 word에서 첫 글자를 뗀 단어 word[1...]을 격자에서 찾아야 한다. word[1...]의 시작 위치는 (y, x)와 인접한 여덟 칸 중 하나일 것이다. 따라서 여덟 경우를 모두 시도하며 답을 찾으면 된다. 

 

기저 사례의 선택

더 이상의 탐색 없이 간단히 답을 낼 수 있는 다음 경우들은 기저 사례로 선택한다.

 

1. 위치 (y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패

2. (1번 경우에 해당하지 않는 경우) 원하는 단어가 한 글자인 경우 항상 성공

간결한 코드를 작성하는 유용한 팁이 있는데, 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하는 것이다. 그러면 함수를 호출하는 시점에서 이런 오류를 검사할 필요가 없다. 재귀 함수는 항상 한군데 이상에서 호출되기 때문에, 이 습관은 반복적인 코드를 제거하는 데 큰 도움이 된다. 따라서 위 두 가지 경우 외에도 현재 위치가 게임판을 벗어난 경우와, 첫 글자가 일치하지 않는 경우를 모두 기저 사례로 선택해 처리하도록 하자.

 

구현

import java.util.Scanner;

public class Boggle {
    
	static final int[] dx = { -1, -1, -1,  1,  1,  1,  0,  0 };
	static final int[] dy = { -1,  0,  1, -1,  0,  1, -1,  1 };

	static char[][] board = new char[5][5];

	// 5x5 보글 게임 판에 해당 위치에서 주어진 단어가 시작하는지를 반환
	static boolean hasWord(int y, int x, String word) {
    
	// 기저사례 1 : 시작 위치가 밖이면 무조건 실패
	if(!inRange(y, x)) return false;
    
	// 기저사례 2 : 첫 글자가 일치하지 않으면 실패
	if(board[y][x] != word.charAt(0)) return false;
    
	// 기저사례 3 : 단어 길이가 1이면 성공
	if(word.length() == 1) return true;
    
	// 인접한 여덟 칸을 검사한다. 
	for(int direction = 0; direction < 8; ++direction) {
		int nextY = y + dy[direction];
		int nextX = x + dx[direction];
		// 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
		if(hasWord(nextY, nextX, word.substring(1)))
			return true;
		}
		return false;
	}

	static boolean inRange(int y, int x) {
		return (x >= 0 && x < 5) && (y >= 0 && y < 5);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// board판 입력
		for(int i = 0; i < 5; ++i) {
			String tmpStr = sc.next();
			for(int j = 0; j < 5; ++j) {
				board[i][j] = tmpStr.charAt(j);
			}
		}

		// 확인할 단어 수 입력
		int testCount = sc.nextInt();
		String[] str = new String[testCount];
		
		// 단어 입력
		for(int i = 0 ; i < str.length; ++i) {
			str[i] = sc.next();
		}

		for(int n = 0; n < str.length; ++n) {
			System.out.print(str[n] + " ");
			boolean isWord = false;
			
			for(int i = 0; i < 5; ++i) {
				for(int j = 0; j < 5; ++j) {
					if(hasWord(i, j, str[n])) {
						isWord = true;
						break;
					}
				}
				if(isWord) break;
			}

			if(isWord) System.out.println("YES");
			else  System.out.println("NO");
		}

	}
}

hasWord()의 처음에서 시작 위치의 범위와 첫 글자 일치 여부를 확인하고 있기 때문에 for문 안에서 별도로 확인을 하지 않아도 된다. 다음 칸의 상대 좌표 목록을 함수 내에 직접 코딩해 넣은 것이 아닌 별도의 변수로 분리해 낸 점도 참고할 만하다.

 

결과

 

시간 복잡도 분석

완전 탐색 알고리즘의 시간 복잡도를 계산하는 것은 비교적 단순하다. 완전 탐색은 가능한 답 후보들을 모두 만들어 보기 때문에, 시간 복잡도를 계산하기 위해서는 가능한 후보의 수를 전부 세어보면 된다.

 

마지막 글자에 도달하기 전에는 주변의 모든 칸에 대해 재귀 호출을 하게 된다. 각 칸에는 최대 여덟 개의 이웃이 있고, 탐색은 단어의 길이 N에 대해 N - 1 단계 진행된다. 따라서 검사하는 후보의 수는 최대 8^(N - 1) = O(8^N)이 되고, 이것이 알고리즘 시간 복잡도가 된다. (엄청 느리다!) 

 

단어 길이에 따라 지수적으로 증가하기 때문에 단어의 길이가 짧은 경우에만 완전 탐색으로 해결할 수 있다.

 

완전 탐색 레시피

어떤 문제를 완전 탐색으로 해결하기 위해 필요한 과정은 대략 다음과 같다. 이 과정이 모든 문제에 항상 적용되는 것은 아니지만, 처음 접근할 때 대략적인 지침은 될 것이다.

 

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다. 만약 시간 안에 계산할 수 없다면 다른 설계 패러다임을 적용해야 한다.

2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.

3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.

4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리한다.