[종만북][알고스팟] BOGGLE(보글 게임) - 브루트포스(BruteForce) + 동적계획법(Dynamic Programming) JAVA

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

algospot.com :: BOGGLE

코드설명

브루트포스(BruteForce) + 동적계획법(Dynamic Programming) 문제입니다.

 

문제에 들어가면 주의사항에 보여지듯, 완전탐색으로 진행하면 시간초과가 발생합니다.

우선, 이후에 나오는 장에서 개선된 방법을 알려주신다고 하니, 시간초과 나는 코드도 그대로 작성했습니다.

 

시간복잡도는 최악의 경우 O(8^(N-1))입니다. 이떄 N은 단어의 길이이겠습니다.

총 8가지 선택지가 있는 N개를 진행하기에 그렇습니다.

 

문제에서 새롭게 배운점입니다.

1. 모든 원소들의 네이밍 방법입니다. 일반적으로 Flag 형식으로 변수를 작성해서했는데, isWord, inRange, hasWord와 같이 상태를 나타내는 단어인 is, in, has를 사용함으로써 더 편하게 이해할 수 있었습니다.

2. String str에서 str.substring(1)을 하면, 지정된 인덱스부터 문자열의 끝까지의 부분 문자열을 반환합니다.

아래와 같은 예시가 있습니다.

public class Main {
    public static void main(String[] args) {
        String word = "example";
        String result = word.substring(1); // 첫 번째 문자 제외
        System.out.println(result); // "xample" 출력
    }
}

이러한 형태로 str.substring(!)을 함으로써 해당 문자열을 받고 처리하기가 훨씬 쉬워졌습니다.

기존에, 이 함수를 몰랐을 경우에는 

문자열을 넘길경우 짜르고서, 새로 선언, 다시 짜르고 새로 선언... 하거나 substring(1, str.length() - 1)로 처리하는것과 같은 방식으로 했어야 했습니다.

JAVA에서 기본타입은 call by value이고, 객체타입은 call by reference 이라는 점을 기억합니다.

String은 기본타입입니다. 그와 반대로, StringBuilder는 참조타입입니다.

 

3. 재귀함수의 반복문 처리 방법입니다.

저는 일반적으로, 다음 변수를 기준으로 단어를 제어해서 조건을 처리하는데, 종만북 저자는 현재 단어 길이를 기준으로 기저 사례를 작성함으로써 처리했습니다.

물론 문제마다 다른 형태가 나오겠지만 이런 방식으로 코드가 훨씬 깔끔한 느낌이 듭니다.

 

4. 기저사례의 순서를 바꿀경우 틀린다는 점을 유의합니다. (이는 언제든지 논리에 따라 바뀔 수 있습니다. str.length() == 0 )를 먼저 처리한다면 상관없겠습니다. 하지만, 이 방식이 재귀함수 호출을 한번씩이라도 더 줄여지기에 더 나은 방법입니다.

//기저사례 1: 범위 벗어날경우
if(isRange(r, c) == false) return false;
//기저사례 2 : 만약 첫 글자가 일치하지 않으면 실패입니다. 
if(gameBoard[r][c] != str.charAt(0)) return false;
//기저사례 3 : 단어의 길이가 1이면 성공입니다. 위의 기저사례 1과 2를 다 통과한뒤 단어의 길이가 1이므로 성공입니다.
if(str.length() == 1) return true;

위의 기저사례를 보듯이, 코드 팁은 먼저 틀린 경우를 모두 나열한 뒤에 마지막에 해당 조건을 모두 통과한 뒤를 처리합니다.

즉, return false로 먼저 필터링한뒤 마지막에 성공조건으로 다시 필터링하라는 의미입니다.

 

5. 재귀함수의 반환 형식입니다. 일반적으로 boolean이 아닌 void로 처리해놓고 전역변수로 값을 바꾸는것이 간단하여 그런 방식을 주로 사용하는데, 반환타입을 boolean 형식으로 하여 재귀함수를 제대로 사용한다면, 코드가 훨씬 깔끔한 것 같습니다

 

6. 반환처리 방식입니다.

아래에 첫번쨰 방식에는 만약 호출한 재귀함수가 true를 반환했다면 바로 종료시킵니다.

//다음 칸이 범위 안에 있는지, 철 글자는 일치하는지 확인할 필요가 없다.
if(hasWord(nr, nc, str.substring(1))) {
    return true;
}

두번쨰 코드는, 모든 코드를 실행한 뒤 논리연산자 |= (OR)을 통해 하나라도 true가 반환되었다면 true로 반환하도록 처리합니다.

    isSuccess |= findWord(nr, nc, target.substring(1));

코드의 속도면에서는 첫번쨰 방식이 일반적으로 더 빠를 것 입니다.

 

 

7. 동적계획법을 활용하여 메모이제이션을 통해 속도를 빠르게 할 수 있습니다.

사실 이 문제의 경우, 처음에 boolean dp[][] 배열로 처리했습니다. 

하지만, 위와 다르게 다음과 같이 int형으로 총 -1 ( 아직 탐색안함) 0 : 탐색했는데 실패 1 :성공 으로 처리합니다.

dp = new int[5][5][target.length()];

 

동적계획법(메모이제이션) 적용시 중요점은 문제를 최적 부분 문제 구조로 바꾸는 것 입니다.

public static int findWord(int r, int c, String target, int idx) {

이 위의 함수를 다음과 같이 정의합니다.

즉, 최적 부분 문제 구조로 바꿈으로써 우리는 DP[][][]를 적용할 수 있습니다.

findWord(int r, int c, String target, int idx) : (r,c)에서 target 문자열을 찾을 수 있는지 반환하라. 
이떄 idx는 target에서 현재 조사하는 문자열의 위치를 의미한다.

 

사실, 처음 이 문제에서 의문이 갔던점은, 오직 한번만 성공하는지 안하는지를 찾는것이 목표이므로, 상태를 단 2가지. 즉 int[][] dp로 처리할 수도 있지 않을까? 라는 생각이 들었습니다. 그래서 똑같이 적용해보았는데, 제출 시에 오답으로 나옵니다. 

이유는, 해당 구간에서 실패했더라도, 새로운 시작점을 기반으로 찾아왔을때는 성공할 수 있다는 것 입니다. 만약 (0,0)에서 시작하여 (2,3)으로 도착하여 실패했던 부분이, (4,3)부분에서 시작하여 다른 공간을 돌아서 왔을때 (2,3)을 경유하여 성공하는 경우가 있는 것 입니다.

 

각 findWord의 재귀함수 호출 부분들이 서로 아예 독립적인 함수로 바라봄으로써 ( (r,c)에서 target(idx~target.length)까지 가능한가를 반환하는 함수, 이전의 target은 전혀 중요하지 않다. ) 가능합니다.

 

또, 이미 불가능함을 판단한 경우, 더이상 탐색하지 않아도 성공한 경우를 미리 반환함으로써 시간초과를 줄일 수 있습니다. ( 사실 이 문제의 경우, 만약 성공한 경우가 존재한다면, 이미 함수가 성공한채로 반환됩니다. 그러므로, 이 DP의 역할은 주로 실패의 경우를 바라봄을 알 수 있습니다. 만약 시작점별로 몇개의 단어가 검색될 수 있는가? 라는 조건으로 나온다면 이 DP[][][]는 더욱 큰 역할을 할 것 입니다.

 

 

 

.

코드

6장까지 읽고 작성한 코드입니다.

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N;
	public static int answer = 0;
	public static char[][] boggle;
	public static String targetWord;
	//상 -> 시계방향으로 회전합니다.
	public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		boggle = new char[5][5];
		while(C-- > 0) {
			for(int i=0;i<5;i++) {
				st = new StringTokenizer(br.readLine());
				boggle[i] = st.nextToken().toCharArray();
			}
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				targetWord = st.nextToken();
				
				boolean isFind = false;
				for(int r=0; r<5;r++) {
					for(int c=0;c<5;c++) {
						isFind = hasWord(r, c, targetWord);
						if(isFind) break;
					}
					if(isFind) break;
				}
				
				if(isFind) System.out.println(targetWord+" "+"YES");
				else System.out.println(targetWord+" "+"NO");
				
			}
		}
		
	}
	
	public static boolean hasWord(int r, int c, String str) {
		
		//기저 사례 1 : 시작 위치가 범위밖이면 무조건 실패.
		if(isRange(r, c) == false) return false;
		//기저 사례 2 : 첫 글자가 일치하지 않으면 실패
		if(str.charAt(0) != boggle[r][c]) return false;
		//기저 사례 3 : 단어 길이가 1이면 성공, 마지막까지 왔다면 성공한 것 입니다.
		if(str.length() == 1) return true;
		
		//인접한 여덞 칸을 검사한다.
		for(int dir = 0; dir < 8; dir++) {
			int nr = r + dx[dir], nc = c + dy[dir];
			//다음 칸이 범위 안에 있는지, 철 글자는 일치하는지 확인할 필요가 없다.
			if(hasWord(nr, nc, str.substring(1))) {
				return true;
			}
		}
		return false;
	}
	
	public static boolean isRange(int r, int c) {
		if(r < 0 || r >= 5 || c < 0 || c >= 5) return false;
		return true;
	}
	
}

기저사례와 마지막 종료 지점 함수를 다르게 풀어본 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static char[][] map;
	public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		map = new char[5][5];
		
		for(int i=0;i<5;i++) {
			st = new StringTokenizer(br.readLine());
			map[i] = st.nextToken().toCharArray();
		}
		
		st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			String target = st.nextToken();
			boolean isSuccess = false;
			for(int r = 0; r < 5; r++) {
				for(int c = 0; c < 5; c++) {
//					visited = new boolean[5][5]; //실수한 부분. 
//					이전 부분에 돌아가서 찾을 수 있다. 즉  지나간 글자를 다시 지나가는 것은 가능하지만
					if(findWord(r, c, target) == true) {
						isSuccess = true;
						break;
					}
				}
				if(isSuccess==true) break;
			}
			if(isSuccess == true)
				System.out.println(target+" "+"YES");
			else
				System.out.println(target+" "+"NO");
		}
		
	}
	
	public static boolean findWord(int r, int c, String target) {
		//기저사례 0 : 만약 target길이가 0 이면 성공이다.
		if(target.length() == 0) return true;
		
		//기저사례 1 : 만약 범위가 벗어난다면 실패한다.
		if(r < 0 || r >= 5 || c < 0 || c >= 5) return false;
		
		//기저사례 2 : 만약 해당 위치가 target의 첫번째 문자와 다르다면 실패이다.
		if(map[r][c] != target.charAt(0)) return false;
		
		boolean isSuccess = false;
		for(int dir = 0; dir< 8; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			isSuccess |= findWord(nr, nc, target.substring(1));
		}
		
		return isSuccess;
	}
	
}

 

동적계획법을 활용한 코드입니다. (dp[][][] 3차원으로 처리해야만 작동한다. dp[][]로 처리할경우 모든 경우를 완전탐색하지 못한다. 성공할 수 있는데 dp[][]로 인해 중단되는 경우 발생)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static char[][] map;
	public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	public static int[][][] dp;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		
		while(C-- > 0) {
			
			map = new char[5][5];
			for(int i=0;i<5;i++) {
				st = new StringTokenizer(br.readLine());
				map[i] = st.nextToken().toCharArray();
			}
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			
			for(int targetWord = 0; targetWord < N; targetWord ++) {
				st = new StringTokenizer(br.readLine());
				String target = st.nextToken();
				boolean isSuccess = false;
				dp = new int[5][5][target.length()];
				
				for(int i=0;i<5; i++) {
					for(int j=0;j<5;j++) {
						Arrays.fill(dp[i][j], -1);
					}
				}
				
				for(int r = 0; r < 5; r++) {
					for(int c = 0; c < 5; c++) {
//					visited = new boolean[5][5]; //실수한 부분.
//					이전 부분에 돌아가서 찾을 수 있다. 즉  지나간 글자를 다시 지나가는 것은 가능하다. 선택하지 않아도 되고 선택해도 된다.
						if(findWord(r, c, target, 0) == 1) {
							isSuccess = true;
							break;
						}
					}
					if(isSuccess==true) break;
				}
				
				if(isSuccess == true)
					System.out.println(target+" "+"YES");
				else if(isSuccess == false)
					System.out.println(target+" "+"NO");
			}
			
		}
	}
	
	public static int findWord(int r, int c, String target, int idx) {
		//기저사례 0 : 만약 target길이가 0 이면 성공이다. 이 방법도 가능하다. 먼저 처리. 그대신 하단의 경우를 주석처리.
		//if(target.length() == 0) return 1;		
		
		//기저사례 1 : 만약 범위가 벗어난다면 실패한다.
		if(r < 0 || r >= 5 || c < 0 || c >= 5) return 0;
		
		//기저사례 2 : 만약 해당 위치가 target의 첫번째 문자와 다르다면 실패이다.
		if(map[r][c] != target.charAt(0)) return 0;
		
		//기저사례 0 : 만약 target길이가 0 이면 성공이다.
		if(target.length() == 1) return 1;		
		
		//메모이제이션
		if(dp[r][c][idx] != -1) return dp[r][c][idx];
		
		for(int dir = 0; dir< 8; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(findWord(nr, nc, target.substring(1), idx + 1) == 1) {
				return dp[r][c][idx] = 1;
			}
		}
		return dp[r][c][idx] = 0;
	}
	
}