문제 풀이 - 보글 게임(JAVA)

보글 게임

문제의 분할

우리가 해결해야 할 문제는 '게임판에서 단어 word가 주어질 때 해당 단어를 찾을 수 있는가?' 입니다. 하지만 해결해야 할 문제를 재귀적으로 해결하기 위해 '게임판에서의 현재 위치 (column, row) 그리고 단어 word가 주어질 때 해당 단어를 이 칸에서부터 시작해서 찾을 수 있는가?'로 바꾼다면 boolean hasWord(int column, int row, String word) 함수로 만들 수 있습니다.
우리는 해당 단어를 이 위치에서 찾을 수 있는지 알기 위해 최대 아홉 가지 정보를 알아야 합니다.

1. 현재 위치 (column, row)에 단어의 첫 글자가 있는가?
2. 윗 칸 (column-1, row)에서 시작해서, 단어의 나머지 글자들을 찾을 수 있는가?
3. 왼쪽 위 칸 (column-1, row-1)에서 시작해서 단어의 나머지 글자들을 찾을 수 있는가?
4. ...
5. ...

이 중 2번 이후의 항목은 원래 문제에서 한 조각을 떼어냈을 뿐, 형식이 같은 또 다른 문제를 푼 결과입니다. 즉 원래 문제의 일부라고 말할 수 있죠. 이런 문제들을 원래 문제의 부분 문제라고 합니다.

기저 사례의 선택

문제를 분할했다면 분할할 수 없는 작은 부분 문제를 처리하기 위해 기저 사례를 선택해야 합니다.

1. 입력된 column과 row가 게임판의 범위를 벗어난 경우 항상 실패
2. 위치 (column, row)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
3. (2번 경우에 해당되지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공

시간 복잡도 분석

한 단어를 찾을 수 있는지 검사하기 위해 검사할 단어의 길이가 1이 아닌 경우에는 항상 8번 재귀 호출을 합니다. 단어의 길이 $N$에 대해 $N-1$단계 진행됩니다. 따라서 시간 복잡도는 $O(8^N)$이 됩니다.

구현

import java.util.*;

public class Main {

    // 문제를 해결하는 데 필요한 전역 변수입니다.
    public static char[][] board = new char[5][5];
    public static int wordCount;
    public static String[] words;
    public static HashMap<String, Boolean> result = new HashMap<String, Boolean>();
    // 상대 좌표를 저장하는 배열입니다.
    public static int[] dr = {-1, -1, -1, 1, 1, 1, 0, 0};
    public static int[] dc = {-1, 0, 1, -1, 0, 1, -1, 1};

    // 테스트 케이스마다 입력값을 받는 함수입니다.
    public static void input(Scanner scanner) {
        for (int i = 0; i < 5; i++) {
            String temp = scanner.next();
            for (int j = 0; j < 5; j++) {
                board[i][j] = temp.charAt(j);
            }
        }

        wordCount = scanner.nextInt();
        words = new String[wordCount];
        result.clear();
        for (int i = 0; i < wordCount; i++) {
            String temp = scanner.next();
            words[i] = temp;
            result.put(temp, false);
        }
        scanner.close();
    }

    // 문제를 해결하는 함수입니다.
    public static void solve() {
        for (String string : words) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (hasWord(i, j, string)) {
                        result.put(string, true);
                    }
                }
            }
        }
    }

    // 게임판에 단어가 존재하는지 여부를 반환하는 함수입니다.
    public static boolean hasWord(int column, int row, String word) {
        // 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
        if (!inRange(column, row)) return false;
        // 기저 사례 2: 첫 글자가 일치하지 않으면 실패
        if (board[column][row] != word.charAt(0)) return false;
        // 기저 사례 3: 단어 길이가 1이면 성공
        if (string.length() == 1) return true;
        // 인접한 여덟 칸을 검사합니다.
        for (int direction = 0; direction < 8; direction++) {
            int nr = row + dr[direction];
            int nc = column + dc[direction];
            // 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없습니다. 기저 사례에서 검사하기 때문입니다.
            if (hasWord(nc, nr, word.substring(1))) {
                return true;
            }
        }
        return false;
    }

    // 선택한 좌표가 게임판의 범위 안에 있는지 확인하는 함수입니다.
    public static boolean inRange(int column, int row) {
        return 0 <= column && column < 5 && 0 <= row && row < 5;
    }

    // 문제의 답을 출력하는 함수입니다.
    public static void output() {
        for (String string : words) {
            if (result.get(string)) {
                System.out.println(string + " YES");
            } else {
                System.out.println(string + " NO");
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int tc = 0; tc < testCase; tc++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고

여러 함수에서 키보드의 입력을 받아야 하는 문제는 처음이라서 처음엔 main함수와 input함수 각각 Scanner의 인스턴스를 생성했습니다. 하지만 main함수에서 생성한 Scanner의 인스턴스를 사용해 입력을 받게 되면 새로 생성한 Scanner의 인스턴스는 이미 입력된 데이터를 받을 수 없습니다. 정확한 이유는 모르지만 아마 Scanner의 인스턴스가 생성되면 새로운 버퍼를 생성하기 때문에 이런 현상이 발생하는 것 같습니다. 이를 해결하기 위해 main함수에서 생성한 Scanner 인스턴스를 input함수의 인자로 넘겨줬습니다.