[BOJ 알고리즘, C++]#9202_Boggle

#1. 문제

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

 

---

 

#2. 풀이

 

1. 백 트래킹

[알고리즘]#6_백 트래킹

백 트래킹 알고리즘은 모든 후보 경로에 대하여 점진적으로 탐색을 진행하며, 현재 경로가 정답으로 이어질 수 없다고 판단될 경우 이전 단계로 돌아가 다른 후보 경로에 대한 탐색을 진행하는 탐색 진행 방색입니다.

 

3. 빈 줄 무시하기

cin.ignore;
cin.ignore;

빈 줄이 입력으로 주어지면 이를 무시하기 위해 cin.ignore를 두 번 호출해 줍니다. 첫 번째 호출은 아직 입력 버퍼에 남아 있는 "\n" 개행 문자를 제거하기 위함이고, 두 번째 호출은 실제 빈 줄 입력을 무시하기 위함입니다.

 

2. 종료 조건 설정 시 주의!

1. 먼저, 단어와 대응되는 점수를 map 컨테이너에 삽입해줍니다.
2. 그리고, 각 입력에 대하여 vector 컨테이너를 통해 board를 구성합니다.
3. 각 borad에 대하여 미로 찾기 유형의 백트래킹을 수행합니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/9202
*   @문제: 4x4 에서 가로, 세로, 대각선 인접한 문자들을 통해 주어진 게임 사전의 단어와 일치하는 문자열 구성.
*   @설명
        1. 백트래킹 종료 조건을 더 세심하게 살펴볼것.
*/

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

typedef pair<int, int> p;

int sum, found;
string maxLengthWord = "";
map<string, int> words;
set<string> wordsFound;

int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};

void dfs(const vector<string>& board, vector<vector<bool>>& visited, int y, int x, string word) {
    if (word.length() > 8) return;  // 단어 길이 제한

    if (words.find(word) != words.end() && wordsFound.find(word) == wordsFound.end()) {
        sum += words[word];
        found++;
        wordsFound.insert(word);
        if (word.length() > maxLengthWord.length() || 
            (word.length() == maxLengthWord.length() && word < maxLengthWord)) {
            maxLengthWord = word;
        }
    }

    for (int i = 0; i < 8; ++i) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4 || visited[ny][nx]) continue;

        visited[ny][nx] = true;
        dfs(board, visited, ny, nx, word + board[ny][nx]);
        visited[ny][nx] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int w;
    cin >> w;

    while (w--) {
        string word;
        cin >> word;
        int score = 0;
        if (word.length() <= 2) score = 0;
        else if (word.length() <= 4) score = 1;
        else if (word.length() == 5) score = 2;
        else if (word.length() == 6) score = 3;
        else if (word.length() == 7) score = 5;
        else if (word.length() == 8) score = 11;
        words[word] = score;
    }

    cin.ignore();
    cin.ignore();

    int b;
    cin >> b;

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

        sum = 0;
        found = 0;
        maxLengthWord = "";
        wordsFound.clear();

        vector<vector<bool>> visited(4, vector<bool>(4, false));
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                visited[i][j] = true;
                dfs(board, visited, i, j, string(1, board[i][j]));
                visited[i][j] = false;
            }
        }

        cout << sum << ' ' << maxLengthWord << ' ' << found << '\n';

        if (b > 0) {
            cin.ignore();
            cin.ignore();
        }
    }

    return 0;

 

---