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

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

목차

문제 : 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';
        }

    }
}

 

 

 

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