[코테] 백준 9202번 : Boggle (java)

https://www.acmicpc.net/problem/9202

알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이

❓문제

---

🔅해석

Trie 알고리즘을 활용하여 문제를 해결한다.

 

먼저, 입력받은 단어들로 Trie를 생성한다.

"ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다.

"ACM"을 담은 Trie

 

for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다.

 

dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다.

 

1. 체크인

visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다.

 

2. 목적지인가

목적지의 기준은 1) 현재 노드가 단어이면서, 2) 이전 찾았던 단어가 아니라면 목적지이다.

정답 처리를 해준다. 이 후 멈추는 것이 아니라 계속 탐색하여 앞글자가 같은 다른 단어도 있는지 확인한다.

 

3. 연결된 곳을 순회

맵을 가로, 세로, 대각선으로 탐색해야하므로  x, y에 대해 방향 배열을 for문으로 순회한다.

//상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
static int[] DX = { 0, 0, -1, 1, -1, 1, -1, 1 };
static int[] DY = { 1, -1, 0, 0, 1, 1, -1, -1 };

 

4. 갈 수 있는가

아래 3가지 조건을 만족해야한다.

1) 인덱스가 맵 인덱스 안에 있다.

2) 현재 노드 자식 중에 다음 입력받을 철자가 존재한다.

3) 방문하지 않았다.

 

5. 간다.

dfs 를 호출할 때, node에는 자식의 노드를 넘긴다.

 

6. 체크아웃

체크인의 반대로 진행한다.

 

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int W, B;
	static char[][] map;
	static boolean[][] visited;
	static TrieNode root;
	static StringBuilder sb;
	static int[] DX = { 0, 0, -1, 1, -1, 1, -1, 1 };
	static int[] DY = { 1, -1, 0, 0, 1, 1, -1, -1 };

	static int score;
	static String maxLen;
	static int cnt;

	static StringBuilder result = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		W = Integer.parseInt(br.readLine());

		root = new TrieNode();
		for (int i = 0; i < W; i++) {
			insert(br.readLine());
		}

		br.readLine();
		B = Integer.parseInt(br.readLine());
		for (int b = 0; b < B; b++) {
			// map 생성
			map = new char[4][4];
			visited = new boolean[4][4];
			sb = new StringBuilder();
			score = 0;
			maxLen = "";
			cnt = 0;

			for (int i = 0; i < 4; i++) {
				String str = br.readLine();
				for (int j = 0; j < 4; j++) {
					map[i][j] = str.charAt(j);
				}
			}

			// 탐색
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					int idx = map[i][j] - 'A';
					if (root.children[idx] != null) {
						dfs(i, j, root.children[idx]);
					}
				}
			}
			root.clearHit();
			result.append(score).append(" ").append(maxLen).append(" ").append(cnt).append("\n");
			if (b < B - 1) {
				br.readLine();
			}
		}

		System.out.println(result.toString());
		br.close();

	}

	private static void dfs(int y, int x, TrieNode node) {
		// 1. 체크인
		visited[y][x] = true;
		sb.append(map[y][x]);

		// 2. 목적지인가
		if (node.isWord && !node.isHit) {
			score += getScore(); // 점수변환
			maxLen = getMaxLen(); // 제일 긴 단어인지
			cnt++;

			node.isHit = true;
		}

		// 3. 연결된 곳을 순회
		for (int i = 0; i < 8; i++) {
			int nextY = y + DY[i];
			int nextX = x + DX[i];

			// 4. 갈수 있는가
			if (isMap(nextY, nextX) && node.children[map[nextY][nextX] - 'A'] != null && !visited[nextY][nextX]) {
				// 5. 간다
				dfs(nextY, nextX, node.children[map[nextY][nextX] - 'A']);
			}
		}

		// 6. 체크아웃
		visited[y][x] = false;
		sb.deleteCharAt(sb.length() - 1);

	}

	private static String getMaxLen() {
		if (maxLen.length() < sb.length()) {
			return sb.toString();
		} else if (maxLen.length() == sb.length()) {
			if (maxLen.compareTo(sb.toString()) > 0) {
				return sb.toString();
			}
		}
		return maxLen;
	}
	
	//글자 수에 따른 점수 반환
	private static int getScore() {
		// 1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점
		int len = sb.length();
		if (len <= 2) {
			return 0;
		} else if (len <= 4) {
			return 1;
		} else if (len <= 5) {
			return 2;
		} else if (len <= 6) {
			return 3;
		} else if (len <= 7) {
			return 5;
		} else {
			return 11;
		}
	}
	
	//map안에 존재하는지 판단하여 반환
	private static boolean isMap(int nextY, int nextX) {
		if (nextY >= 4 || nextY < 0 || nextX >= 4 || nextX < 0) {
			return false;
		}

		return true;
	}
	
	//트라이 
	private static void insert(String word) {
		TrieNode current = root;
		for (int i = 0; i < word.length(); i++) {
			int wordIndex = word.charAt(i) - 'A';
			if (current.children[wordIndex] == null) {
				current.children[wordIndex] = new TrieNode();
			}
			current = current.children[wordIndex];
		}
		current.isWord = true;
	}

}

class TrieNode {
	TrieNode[] children = new TrieNode[26];
	boolean isWord;
	boolean isHit;

	void clearHit() {
		isHit = false;
		for (int i = 0; i < children.length; i++) {
			if (children[i] != null) {
				children[i].clearHit();
			}
		}
	}
}

 

---

❗결과