[BaekJoon] 9202번 - Boggle [Java][C++]

문제 링크

---

1. 문제 풀이

단어 사전에 들어있는 단어들이 주어진 후 여러 개의 Boggle 보드들이 주어진다. 각 보드에서 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 구해야 하는데 트라이 자료구조를 활용하면 해결할 수 있다.

먼저 단어 사전의 단어들로 트라이를 생성한다. 이때 Boggle에서 단어 사전에 등재되었는지 여부를 구해야하므로 해당 단어의 끝 여부도 표시해야 하는데 이를 1로 표시했다.

이후 각 보드에 대해 $(0,\ 0)$ 부터 $(3,\ 3)$ 까지 16칸에 대해 매번 단어의 시작점으로 잡고 DFS 탐색을 해줬다. DFS는 보드 내 좌표와 현재까지 완성한 단어, 노드 번호를 파라미터로 가지며 모든 단어 조합을 탐색해야하므로 방문 체크 후 방문 해제를 하는 방식으로 했다. 현재 노드 번호가 단어의 끝일 경우 최대 점수, 가장 긴 단어, 찾은 단어의 수를 갱신해주면 되는데 이때 한번 찾았던 단어를 중복 비교하는 것을 막기 위해 mark라는 변수를 두어서 첫 번째 보드부터 2로 마킹을 해줬다. chk 값이 0보다 크면 일단 단어의 끝인데 mark와 동일하면 현재 보글에서 찾은 적이 있는 단어이므로 중복 계산을 하지 않을 수 있다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {

    static final int MX = 1 + 300000 * 8;
    static final int ROOT = 0;
    static int unused = ROOT + 1;
    static int[][] nxt = new int[MX][26];
    static int[] chk = new int[MX];
    static int mark = 2;

    static int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dc = {-1, 0, 1, 1, 1, 0, -1, -1};
    static char[][] grid = new char[4][4];
    static boolean[][] visited = new boolean[4][4];
    static int[] score = {0, 0, 0, 1, 1, 2, 3, 5, 11};

    static int point;  // 최대 점수
    static String longest;  // 가장 긴 단어
    static int cnt;  // 찾은 단어의 개수

    static void insert(String s) {
        int cur = ROOT;
        for (char c : s.toCharArray()) {
            int idx = c - 'A';
            if (nxt[cur][idx] == 0) nxt[cur][idx] = unused++;
            cur = nxt[cur][idx];
        }
        chk[cur] = 1;
    }

    static void find(int r, int c, int cur, StringBuilder word) {
        visited[r][c] = true;

        if (0 < chk[cur] && chk[cur] < mark) {
            chk[cur] = mark;

            point += score[word.length()];
            if (word.length() > longest.length() || (word.length() == longest.length() && word.toString().compareTo(longest) < 0)) {
                longest = word.toString();
            }
            cnt++;
        }

        for (int d = 0; d < 8; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue;
            if (visited[nr][nc]) continue;

            int idx = grid[nr][nc] - 'A';
            if (nxt[cur][idx] == 0) continue;

            word.append(grid[nr][nc]);
            find(nr, nc, nxt[cur][idx], word);
            word.deleteCharAt(word.length() - 1);
        }

        visited[r][c] = false;
    }

    static void solve(int r, int c) {
        int idx = grid[r][c] - 'A';
        if (nxt[ROOT][idx] == 0) return;

        StringBuilder word = new StringBuilder();
        word.append(grid[r][c]);
        find(r, c, nxt[ROOT][idx], word);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int w = Integer.parseInt(br.readLine());
        while (w-- > 0) {
            insert(br.readLine());
        }
        br.readLine();

        int b = Integer.parseInt(br.readLine());
        while (b-- > 0) {
            for (int i = 0; i < 4; i++) {
                grid[i] = br.readLine().toCharArray();
            }
            if (b != 0) br.readLine();

            point = 0;
            longest = "";
            cnt = 0;

            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    solve(i, j);
                }
            }

            sb.append(point).append(" ").append(longest).append(" ").append(cnt).append("\n");
            mark++;
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 300000 * 8;
const int ROOT = 0;
int unused = ROOT + 1;
int nxt[MX][26];
int chk[MX];
int mark = 2;

int dr[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dc[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
char grid[5][5];
bool visited[4][4];
int score[9] = {0, 0, 0, 1, 1, 2, 3, 5, 11};

int point;       // 최대 점수
string longest;  // 가장 긴 단어
int cnt;         // 찾은 단어의 개수

void insert(string& s) {
    int cur = ROOT;
    for (char c : s) {
        int idx = c - 'A';
        if (nxt[cur][idx] == 0) nxt[cur][idx] = unused++;
        cur = nxt[cur][idx];
    }
    chk[cur] = 1;
}

void find(int r, int c, int cur, string& s) {
    visited[r][c] = true;

    if (0 < chk[cur] && chk[cur] < mark) {
        chk[cur] = mark;

        point += score[s.size()];
        if (s.size() > longest.size() || (s.size() == longest.size() && s < longest)) {
            longest = s;
        }
        cnt++;
    }

    for (int d = 0; d < 8; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];

        if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue;
        if (visited[nr][nc]) continue;

        int idx = grid[nr][nc] - 'A';
        if (nxt[cur][idx] == 0) continue;

        s += grid[nr][nc];
        find(nr, nc, nxt[cur][idx], s);
        s.pop_back();
    }

    visited[r][c] = false;
}

void solve(int r, int c) {
    int idx = grid[r][c] - 'A';
    if (nxt[ROOT][idx] == 0) return;

    string s;
    s.push_back(grid[r][c]);
    find(r, c, nxt[ROOT][idx], s);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int w;
    cin >> w;
    while (w--) {
        string s;
        cin >> s;
        insert(s);
    }

    int b;
    cin >> b;
    while (b--) {
        for (int i = 0; i < 4; i++) {
            cin >> grid[i];
        }

        point = 0;
        longest = "";
        cnt = 0;

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                solve(i, j);
            }
        }

        cout << point << ' ' << longest << ' ' << cnt << '\n';
        mark++;
    }
}

---