본문 바로가기
Study/알고리즘 문제해결전략(종만북)

[종만북] BOGGLE - 보글 게임 (자바, C++)

by Nahwasa 2023. 3. 20.

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

    문제 : aoj-BOGGLE

     

     

    풀이

      전체적인 로직은 다음과 같다.

    A. 보글 게임판을 입력받는다.

    B. N개의 각 단어에 대해, 각 문자와 동일한 보글 게임판의 문자 위치를 찾는다.

    C. 이후 각 단어의 모든 문자를 찾을 수 있는 동안 보글 게임판의 현재 위치에서 8방향으로 탐색을 진행한다.

    D. 모든 문자를 찾았다면 YES, 아니면 NO 이다.

     

      위와 같이 완전탐색으로 진행하면 O(C x N * 8^10) 정도의 시간이 필요하므로 풀 수 없다(10은 단어의 길이를 뜻한다). 그래서 좀 더 줄여봐야 한다.

    • 우선 'A'를 입력받으면서 모든 대문자(26개)에 대해 존재유무를 체크해둔다. -> N개의 문자에 체크해둔 문자에 없는 문자가 등장한다면 탐색을 해보지 않아도 불가함을 알 수 있다. -> 다만 이건 부가적인 예외처리일 뿐 전체적인 시간복잡도에 영향을 끼치진 않는다. 
    for (int i = 0; i < str.length(); i++) {
        if (!chk[atoi(str.charAt(i))])
            return false;
    }

     

     

    • 이미 왔던 곳을 방문체크한다.

      그럼 어떻게 방문체크를 해야할지 정해야 한다. '지나간 글자를 다시 지나가는 것은 가능' 라고 했으므로 단순히 게임판의 특정 위치에 도착했음을 2차원 배열로 확인하는 것 만으론 처리가 불가하다. 내 경우엔 거기에 현재 보고 있는 단어의 인덱스를 추가한 3차원 배열로 확인했다 (v[r][c][idx]. 말로 설명해보면 "해당 단어의 idx번 문자로 이전에 이미 (r, c) 위치에 온 적 있다"가 된다. 따라서 대략 O(C x N x 10 x 5^2) 정도로 가능하다.

    if (nr<0 || nr>=BOARD_SIZE || nc<0 || nc>=BOARD_SIZE || board[nr][nc] != next || v[nr][nc][idx])
    	continue;

     

     

    코드(java) : github

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    
    public class Main {
    
        private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        private static final StringBuilder answer = new StringBuilder();
        private static final int BOARD_SIZE = 5;
        private static final int A_TO_Z = 'Z'-'A'+1;
    
        private char[][] board;
        private boolean[] chk;
    
        public static void main(String[] args) throws Exception {
            int c = Integer.parseInt(br.readLine());
            Main main = new Main();
            while (c-->0) main.solution();
            System.out.print(answer);
        }
    
        public void solution() throws Exception {
            initializeBoard();
    
            int n = Integer.parseInt(br.readLine());
            while (n-->0) {
                String str = br.readLine();
                answer.append(str).append(' ');
                answer.append(isPossibleToFind(str) ? "YES" : "NO").append('\n');
            }
        }
        
        private void initializeBoard() throws Exception {
            board = new char[BOARD_SIZE][BOARD_SIZE];
            chk = new boolean[A_TO_Z];
            
            for (int i = 0; i < BOARD_SIZE; i++) {
                String row = br.readLine();
                for (int j = 0; j < BOARD_SIZE; j++) {
                    char c = row.charAt(j);
                    chk[atoi(c)] = true;
                    board[i][j] = c;
                }
            }
        }
    
        private boolean isPossibleToFind(String str) {
            for (int i = 0; i < str.length(); i++) {
                if (!chk[atoi(str.charAt(i))])
                    return false;
            }
    
            char first = str.charAt(0);
            boolean[][][] v = new boolean[BOARD_SIZE][BOARD_SIZE][str.length()];
            for (int i = 0; i < BOARD_SIZE; i++) {
                for (int j = 0; j < BOARD_SIZE; j++) {
                    if (board[i][j] != first || !find(str, v,1, i, j)) continue;
                    return true;
                }
            }
            return false;
        }
    
        private boolean find(String str, boolean[][][] v, int idx, int r, int c) {
            if (idx == str.length())
                return true;
    
            char next = str.charAt(idx);
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (i==0 && j==0) continue;
                    int nr = r+i;
                    int nc = c+j;
                    if (nr<0 || nr>=BOARD_SIZE || nc<0 || nc>=BOARD_SIZE || board[nr][nc] != next || v[nr][nc][idx])
                        continue;
    
                    v[nr][nc][idx] = true;
                    if (find(str, v, idx+1, nr, nc))
                        return true;
                }
            }
    
            return false;
        }
    
        private int atoi(char c) {
            return c-'A';
        }
    }

     

     

    코드(cpp) : github

    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int BOARD_SIZE = 5;
    const int A_TO_Z = 'Z'-'A'+1;
    char board[BOARD_SIZE][BOARD_SIZE] = {0};
    bool chk[A_TO_Z] = {0};
    bool v[BOARD_SIZE][BOARD_SIZE][10];
    
    bool find(string str, int idx, int r, int c) {
        if (idx == str.length())
            return true;
    
        char next = str[idx];
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i==0 && j==0) continue;
                int nr = r+i;
                int nc = c+j;
                if (nr<0 || nr>=BOARD_SIZE || nc<0 || nc>=BOARD_SIZE || board[nr][nc] != next || v[nr][nc][idx])
                    continue;
    
                v[nr][nc][idx] = true;
                if (find(str, idx+1, nr, nc))
                    return true;
            }
        }
    
        return false;
    }
    
    bool isPossibleToFind(string str) {
        memset(v, false, sizeof(v));
    
        int len = str.length();
        for (int i = 0; i < len; i++) {
            if (!chk[str[i]-'A'])
                return false;
        }
    
        char first = str[0];
    
    
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] != first || !find(str, 1, i, j)) continue;
                return true;
            }
        }
        return false;
    }
    
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int c;
        cin >> c;
        while (c--) {
    
            for (int i = 0; i < BOARD_SIZE; i++) {
                string row;
                cin >> row;
                for (int j = 0; j < BOARD_SIZE; j++) {
                    chk[row[j]-'A'] = true;
                    board[i][j] = row[j];
                }
            }
    
            int n;
            cin >> n;
            while (n--) {
                string str;
                cin >> str;
                cout << str << " " << (isPossibleToFind(str) ? "YES" : "NO") << '\n';
            }
    
        }
    }

     

     

     

    ※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.

    댓글