[종만북] 보글 게임 with Java

[ 문제 ]

5 X 5 크기의 알파벳 격자를 가지고 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것. 한 글자가 두 번 이상 사용될수도 있음.

 

재귀함수가 무엇인지 이해할 수 있었던 문제.

 

package jongman.bruteForce;

public class Boggle {

	//@1.
    static int[] dx = { -1, -1, -1, 1, 1, 1, 0, 0 };
	static int[] dy = {-1, 0, 1, -1, 0, 1, -1, 1 };
	static char[][] board = {
			{'U', 'R', 'L', 'P', 'M'},
			{'X', 'P', 'R', 'E', 'T'},
			{'G', 'I', 'A', 'E', 'T'},
			{'X', 'T', 'N', 'Z', 'Y'},
			{'X', 'O', 'Q', 'R', 'S'}
	};
	
	public static void main(String[] args) {
		String word = "PRETTY";
		int x = 1;
		int y = 1;
		boolean answer = hasWord(y, x, word);
		System.out.println("answer : " + answer);
	}
	//@2.
	public static boolean hasWord(int y, int x, String word) {
		System.out.println(x + ", " + y);
        //@2-1.
		// 기저사례1 : 시작 위치가 범위 밖이면 무조건 실패 
		if(!inRange(x, y)) {
			System.out.println("범위를 벗엉남 ");
			return false;
		}
        //@2-2.
        // 기저사례2 : 첫 글자가 일치하지 않으면 실패
		if(board[x][y] != word.charAt(0)) {
			return false;
			
		}
        //@2-3.
        // 기저사례3 : 단어 길이가 1이면 성공 
		if(word.length() == 1)
			return true;
		
		//@3.
		for(int direction = 0; direction < 8; ++direction) {
			// 해당 글자를 기준(0, 0)으로 반복문으로 다음글자 찾기 
			int nextY = y + dy[direction];
			int nextX = x + dx[direction];
			//@3-1.
			if(hasWord(nextY, nextX, word.substring(1)))
				return true;
		}
		return false;
	}
	
	public static boolean inRange(int x, int y) {
		if(x >= 0 && x < 5 && y >= 0 && y < 5) {
			return true;
		}
		return false;
	}
}

 

[ 풀이 ]

 

@1. 

(0, 0) 기준으로 움직일 수 있는 범위를 지정. 

x, y 좌표의 범위를 정해준다.

대각선까지 움직일 수 있으므로 3x3 범위 내에서만 움직일 수 있다.

 

@2.

단어를 찾았는지 여부를 bool 값으로 알려주는 함수.

@2-1.

0 ~ 4 사이에 x 와 y 값이 위치하는지 판단하는 inRange 함수 호출.

@2-2.

만약 실제 해당 위치에 있는 값(board[x][y]) 가 찾고자하는 값(word.charAt(0)) 과 다르면 실패. 밑의 @3. 반복문으로 돌아와 이어서 돌게된다.

@2-3.

마지막으로 남은 글자가 한 글자인 경우 밑의 반복문으로 가지 않고 바로 성공 반환. 앞에서 범위를 벗어난 경우와 첫글자가 일치하지 않을 경우를 모두 걸러냈기때문에 @2-3까지 온다는건 현재 탐색 위치에 있는 글자와 찾고있는 글자가 같고, 마지막으로 찾는 글자일 경우이니 무조건 성공이다.

 

@3.

위의 조건문들에서 걸러지지 않고 여기까지 왔다는건 해당 글자를 찾았다는것. 

해당 글자의 위치를 기준으로 다시 3x3 범위 내에서 탐색한다. 

첫 글자는 찾았으니 첫글자를 제외한 남은 글자들을 substring으로 잘라내어 hasWord 함수를 다시 호출한다.

재귀함수이기때문에 만약 다음글자에서 다다음글자를 못찾는다면 이전 반복문으로 돌아와 이어서 수행한다.

무슨말이냐 하면, board를 보면 첫글자 P의 위(0,1)와 오른쪽(1, 2)에 모두 다음글자인 R이 있다.

근데 dx, dy 순으로 탐색하기때문에 위(0,1)에 위치한 R을 먼저 찾아내게 된다.

하지만 위에 위치한 R은 다음글자인 E를 3x3 반경에서 찾을 수 없다. 

for문을 모두 돌아도 E를 찾을 수 없기때문에 다시 먼저 호출되었던 for문으로 돌아와 또다른 R을 찾게되고, 결국 (1,2)에 위치한 R을 찾게된다.