백준 9202 - Boggle

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

9202번: Boggle

---

접근방법

결론적으로 문제를 정리해보면 다음과 같다.

단어는 인접한 글자로 만들 수 있다.
한 블록(주사위)은 각 단어에 한 번까지만 사용가능하다.
단어를 만들면 그 단어의 길이에 따라 점수를 부여받는다.
주어진 Boggle grid에서 받을 수 있는 최대 점수와 찾을 수 있는 가장 긴 단어와 찾은 단어의 수를 구해라!

주의점
한 boggle에서 같은 단어 여러 번 찾기 불가능하다.
답이 없는 경우는 없다.
가장 긴 단어가 여러 개면 사전 순으로 앞서는 것을 출력해야 한다.

문제를 잘 해석해보면 최대라는 말에는 신경쓸 필요가 없다.

각 블록들을 각 단어들에 한 번씩 사용할 수 있다.

즉, 다른 단어들이 블록을 사용했는가 하지 않았는가는 신경쓰지 않고,

특정 단어가 주어진 Boggle 보드(grid)에서 조합이 가능하면

점수를 추가해주고, 가장 긴 단어인지 아닌지 검사하고, 찾은 단어 개수를 증가시켜주면 된다.

---

의사코드

이를 의사코드로 나타내면 다음과 같다.

입력받기:
	단어개수 및 단어목록 입력받기
    
	보드 개수 입력받기
	보드개수만큼 반복:
		보드 입력받기:
			단어목록 초기화
			점수 = 0
			찾은단어개수 = 0
			가장긴단어 = ""
			점수_찾은단어개수_가장긴단어_찾기()
			답 = 점수 + " " + 가장긴단어 + " " + 찾은단어개수
        
	답 출력

일단 입력받는 부분을 확인해보면 재밌는 점은 입력받으면서 답을 바로 구한다는 것이다.

참고로 나는 자바에서 이 부분을 BufferedWriter를 활용해 성능을 최적화하였다.

이제 가장 핵심적인 부분이라고 할 수 있는 `점수_찾은단어개수_가장긴단어_찾기()` 함수를 살펴보겠다.

 

점수_찾은단어개수_가장긴단어_찾기():
    행 = 0 ~ 4 반복:
        열 = 0 ~ 4 반복:
            idx = 0 ~ 단어목록 최대 Index까지 반복:
                첫 글자가 보드[행][열]과 같으면:
                    인접글자로_조합가능한지_검사(행, 열, 단어목록[idx], 1) == true:
                        점수 = 단어길이에 따라 계산
                        가장긴단어보다 단어길이가 길다면:
                            가장긴단어 = 단어목록[idx]
                        가장긴단어와 단어길이가 같다면:
                            가장긴단어 = 사전적으로 더 빠른 단어
                        찾은단어개수++
                        단어목록[idx] = " "
                        
인접글자로_조합가능한지_검사(행, 열, 단어, 검사할단어Idx):
    검사할단어Idx가 == 최종Idx + 1:
    	return true
    방문여부[행][열] = true
    
    행과 열을 기준으로 인접한 좌표들 찾아서 반복:
    	방문여부[인접좌표행][인접좌표열] == false
            보드[인접좌표행][인접좌표열] == 단어의 검사할단어Idx번째 문자이면:
                인접글자로_조합가능한지_검사(인접좌표행, 인접좌표열, 단어, 검사할단어Idx + 1) == true:
                	방문여부[행][열] = false
                	return true
    
    
    방문여부[행][열] = false
    return false

 

`점수_찾은단어개수_가장긴단어찾기()` 함수에서는 `인접글자로_조합가능한지_검사()` 함수를 호출하여

인접글자로 조합가능한지 검사하고, 가능하다면 점수, 가장긴단어, 찾은단어개수를 적절하게 수정한다.

또한 찾은 단어목록의 단어는 " "으로 초기화해주는데, 이는 찾은 단어를 또 찾지 않도록 해주기 위함이다.

 

`인접글자로_조합가능한지_검사()` 함수는 DFS 방식을 통해 각 좌표들을 탐색한다.

탐색하다가 최종Idx + 1과 검사할단어Idx가 일치하게 되면

단어의 각 자리들을 검사하여 모두 통과했음을 의미하므로 true를 반환한다.

또한 한 번 true를 반환하면 그 함수를 호출한 나머지 함수들도 계속해서 true를 반환해서
최종적으로 호출한 부분에도 true가 반환되게 된다.

그 외의 상황에서는 false를 반환하게 된다.

---

JAVA Code

복잡한 내 코드를 조금이나마 쉽게 이해시켜보고자 수도코드를 작성해보았다.

자바로 작성한 코드를 살펴보자~

 

import java.io.*;

public class Main {
    private static String words[], longestWord;
    private static boolean[][] visited = new boolean[4][4];
    private static char[][] board = new char[4][4];
    private static int score, passedwordsCnt;

    // 백준 9202 - Boggle
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int wordsCnt = strToInt(br.readLine());
        String wordsSource[] = new String[wordsCnt];
        for (int i = 0; i < wordsCnt; i++) wordsSource[i] = br.readLine();

        br.readLine();

        int boggleBoardCnt = strToInt(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out), 20 * boggleBoardCnt);
        while (boggleBoardCnt > 0) {
            for (int j = 0; j < 4; j++) board[j] = br.readLine().toCharArray();
            words = wordsSource.clone();
            score = 0;
            passedwordsCnt = 0;
            longestWord = "";
            checkBoard();
            bw.write(score + " " + longestWord + " " + passedwordsCnt + "\n");
            if (boggleBoardCnt != 1) br.readLine();
            boggleBoardCnt--;
        }
        bw.flush();
    }

    private static void checkBoard() {
        for (int row = 0; row < 4; row++)
            for (int col = 0; col < 4; col++)
                for (int i = 0; i < words.length; i++) {
                    if (words[i].charAt(0) == board[row][col] && boardContains(row, col, i, 1)) {
                        int wordLen = words[i].length();
                        if (wordLen <= 5) score += (wordLen - 1) / 2;
                        else if (wordLen == 6) score += 3;
                        else if (wordLen == 7) score += 5;
                        else score += 11;

                        if (longestWord.length() < wordLen) longestWord = words[i];
                        else if (longestWord.length() == wordLen) longestWord = longestWord.compareTo(words[i]) < 0 ? longestWord : words[i];

                        words[i] = " ";
                        passedwordsCnt++;
                    }
                }
    }

    private static boolean boardContains(int row, int col, int wordsIdx, int checkIdx) {
        if (checkIdx == words[wordsIdx].length()) return true;
        visited[row][col] = true;

        for (int i = -1; i < 2; i++)
            for (int j = -1; j < 2; j++) {
                int nextRow = row + i, nextCol = col + j;
                if (nextRow > 3 || nextRow < 0 || nextCol > 3 || nextCol < 0) continue;
                if (!visited[nextRow][nextCol] && board[nextRow][nextCol] == words[wordsIdx].charAt(checkIdx))
                    if (boardContains(nextRow, nextCol, wordsIdx, checkIdx + 1)) {
                        visited[row][col] = false;
                        return true;
                    }
            }

        return visited[row][col] = false;
    }

    private static int strToInt(String str) {
        return Integer.parseInt(str);
    }
}