[BOJ] 백준 9202번 Boggle (Java)

#9202 Boggle

난이도 : 플레 5

유형 : 문자열 / 트라이 / DFS

9202번: Boggle

▸ 문제

상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다.

상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.

Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.

1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.

단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.

그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나  있다.

▸ 출력

각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

 

문제 풀이  

트라이와 그래프 탐색이 합쳐진 문제이다. BFS로도 풀이가 가능하지만 여러 변수들의 상태 값 처리가 그리 간단하지 않다. 이러한 유형은 DFS로 깊이 탐색 방법으로 접근하는 것이 맞다고 생각한다.

 

설계 자체는 간단한데 데이터 처리에서 꽤나 애를 먹었다.

• 재귀 깊이가 깊어짐에따라 StringBuilder로 여태까지 탐색한 문자열 값들을 저장하면 20%에서 실패한다. 그런데 String으로 값을 처리하면 성공한다. 둘다 주소 값을 참조하는 변수라서 데이터 자체에 대한 문제는 아니다.
  
  • StringBuilder nb = sb.appned(map[ny][nx]);  → nb.toString();
  • 디버깅을 해보면 isLatin1()에서 런타임 에러가 발생하는 것으로 보아 StringBuilder.toString() 리턴 과정에서 데이터 값이 잘못 인식되어 반환되는 것으로 추측된다.
    • return isLatin1() ? StringLatin1.newString(value, 0, count) : StringUTF16.newString(value, 0, count);
  • String nxt = str+map[ny][nx];  그래서 그냥 이렇게 처리해주면 제대로 동작한다.
• 그리고 List로 contains() 메서드와 add()메서드를 사용해서 찾은 단어를 저장하면 시간초과가 발생한다. Set으로 처리한 다음 후에 정렬할 때 List를 사용해줘야 한다.

 

설계 및 구현

1. W개의 단어를 트라이 자료구조에 저장한다. trie.insert(in);
2. 주어진 4x4 Boggle 맵을 8가지 방향으로 DFS 탐색한다. search(j,i, ""+ map[i][j]);
   1. 탐색된 문자열이 트라이에 존재하지 않으면 탐색 종료한다.
   2. 탐색된 문자열이 트라이에 존재하고 terminal까지 도달하면 자료구조 Set에 저장한다. resultSet.add(str);
3. 최종으로 저장된 Set을 List 자료구조로 변경 후 정렬하여 최대 점수, 가장 긴 단어(사전 순으로), 찾은 단어 개수를 출력한다.

 

트라이에 구현한 메서드

insert(String word)

• word 문자열을 트라이 자료구조에 저장해준다.

public void insert(String word) {
	TrieNode curNode = this;
	for(int i=0; i<word.length(); i++) {
		char c = word.charAt(i);
		curNode.childNode.putIfAbsent(c, new TrieNode());
		curNode = curNode.childNode.get(c);
		if(i==word.length()-1) {
			curNode.terminal=true;
		}
	}
}

 

isInitWord(char init)

• Map을 탐색하는 초기 조건으로 첫 노드에 해당 init 문자가 존재하는지 체크한다.

public boolean isInitWord(char init) {
	TrieNode trieNode = this;
	for(char c : trieNode.childNode.keySet()) {
		if(init == c) return true;
	}
	return false;
}

 

contains(String word, boolean flag)

• word라는 문자열이 트라이 자료구조에 존재하는지 체크한다. flag 상태에 따라 탐색 정도가 달라진다.
  • flag == true, 전체 문자열을 확인하는 메서드로 동작한다.
  • flag == false, 포함되는 문자열인지 확인하는 메서드로 동작한다.

public boolean contains(String word, boolean flag) { 
	if(word.length() >8) return false;
	TrieNode trieNode = this;
	for(int i=0; i<word.length(); i++) {
		char c= word.charAt(i);
		TrieNode node = trieNode.childNode.get(c);
		if(node == null) {
			return false;
		}
		trieNode = node;
	}
    
	if(flag) { // 전체 문자열인지 확인 
		return trieNode.terminal; 
	}
	else return true; // 포함된 문자열인지만 확인 
}

 

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {

	static TrieNode trie;
	static char[][] map;
	static boolean[][] check;
	static Set<String> resultSet;
	static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
	static int[] dy = {1, 1 ,0 ,-1 ,-1 ,-1, 0, 1};
	static class TrieNode{
		Map<Character, TrieNode> childNode = new HashMap<>();
		boolean terminal;
		
		public TrieNode() {
			/* no-op */
		}
		
		public void insert(String word) {
			TrieNode curNode = this;
			for(int i=0; i<word.length(); i++) {
				char c = word.charAt(i);
				curNode.childNode.putIfAbsent(c, new TrieNode());
				curNode = curNode.childNode.get(c);
				if(i==word.length()-1) {
					curNode.terminal=true;
				}
			}
		}
		
		public boolean isInitWord(char init) {
			TrieNode trieNode = this;
			for(char c : trieNode.childNode.keySet()) {
				if(init == c) return true;
			}
			return false;
		}
	
		public boolean contains(String word, boolean flag) { 
			if(word.length() >8) return false;
			TrieNode trieNode = this;
			for(int i=0; i<word.length(); i++) {
				char c= word.charAt(i);
				TrieNode node = trieNode.childNode.get(c);
				if(node == null) {
					return false;
				}
				trieNode = node;
			}
			
			if(flag) { // 전체 문자열인지 확인 
				return trieNode.terminal; 
			}else return true; // 포함된 문자열인지만 확인 
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int w = Integer.parseInt(br.readLine());
		trie = new TrieNode();
		for(int i=0; i<w; i++) {
			String in = br.readLine();
			trie.insert(in);
		}
		
		br.readLine();
		int b = Integer.parseInt(br.readLine());
		for(int t=0; t<b; t++) {
			
			map = new char[4][4]; 
			for(int i=0; i<4; i++) {
				String line = br.readLine();
				for(int j=0; j<4; j++) {
					char c = line.charAt(j);
					map[i][j] = c;
				}
			}
			
			// map 탐색
			resultSet = new HashSet<>();
			check = new boolean[4][4];
			for(int i=0; i<4; i++) {
				for(int j=0; j<4; j++) {
					if(trie.isInitWord(map[i][j])) {
						check[i][j] = true;
						search(j,i, ""+ map[i][j]);
						check[i][j] = false;
					}
				}
			}
			
			List<String> resultList = new ArrayList<>(resultSet);
			Collections.sort(resultList);
			int cnt = 0;
			int maxLen= 0;
			int idx=0;
			for(int i=0; i<resultList.size(); i++) {
				int len = resultList.get(i).length();
				if(maxLen < len) {
					idx = i;
					maxLen = len;
				}
				cnt += getScore(resultList.get(i));
			}
			
			sb.append(cnt+" " + resultList.get(idx)+" "+ resultList.size()+"\n");
			if(t != b-1) br.readLine();
		}
		System.out.println(sb.toString());	
		
	}
	
	static void search(int x, int y, String str) {
		if(trie.contains(str, true)) {
			resultSet.add(str);
		}
		
		for(int d=0; d<8; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(nx <0 || ny <0 || nx >3 || ny >3) continue;
			if(check[ny][nx]) continue;
			
			String nxt = str + map[ny][nx];
			if(trie.contains(nxt, false)) {
				check[ny][nx] = true;
				search(nx, ny, nxt);
				check[ny][nx] = false;
			}
		}
	}
	
	static int getScore(String word) {
		if(word.length()<=2) return 0;
		else if(word.length()<=4) return 1;
		else if(word.length()==5) return 2;
		else if(word.length()==6) return 3;
		else if(word.length()==7) return 5;
		else if(word.length()==8) return 11;
		
		return 0;
	}
}