C++ 2D 문자 배열에서 주어진 문자열 개수 세기

다음 문제는 신문의 일일 십자말풀이에서 볼 수 있는 유형의 예제입니다. 2차원 문자 배열(미로)이 주어졌을 때, 그 안에서 주어진 단어를 찾아내는 것이 문제입니다. 탐색 알고리즘은 위에서 아래로, 오른쪽에서 왼쪽으로 그리고 그 반대 방향으로 개별 문자를 찾되, 대각선 방향은 제외합니다.

예제로 이해하기

입력 - 찾을 문자열 word: LAYS

2D 문자열 배열 - { "LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS" };

출력 - 2D 문자 배열에서 주어진 문자열의 개수: 7

설명 - 문자열 배열이 주어지면 그중에서 "LAYS"라는 단어를 찾아야 합니다. 이 단어는 위→아래, 오른쪽→왼쪽, 아래→위, 왼쪽→오른쪽 등 어떤 방향으로든 검색할 수 있습니다. 코드의 카운터 플래그는 검색 문자열이 발견될 때마다 증가하며, 마지막에 총 개수가 결과로 반환됩니다. 예제에서 LAYS는 다음과 같이 7번 형성됩니다.

1->LOAPYS → 왼쪽에서 오른쪽으로

2->SAYAOL → 오른쪽에서 왼쪽으로

3->LAYSST → 왼쪽에서 오른쪽으로

4->MLVAYS → 왼쪽에서 오른쪽으로

5->LAYSAA → 왼쪽에서 오른쪽으로

6->LAOYLS → 왼쪽에서 오른쪽으로

7->아래에서 위로 방향의 LAYS

입력 - 찾을 문자열 word: CAMP

2D 문자열 배열 - { "BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL" }

출력 - 2D 문자 배열에서 주어진 문자열의 개수: 0

설명 - 이번에도 문자열 배열 안에서 "CAMP"라는 단어를 위→아래, 오른쪽→왼쪽, 아래→위, 왼쪽→오른쪽 등 네 방향으로 검색하지만, 이 예제에서는 해당 단어가 0번 나타납니다.

프로그램에서 사용된 접근 방식

• 찾을 문자열(word)과 문자열 배열이 몇 가지 유틸리티 변수와 함께 findString() 함수로 전달되어 처리를 시작합니다.
• 행렬의 문자들을 순회하면서 한 문자를 선택해 검색의 시작점으로 삼습니다.
• 선택된 문자를 기준으로 알고리즘에 따라 가능한 모든 방향(상·하·좌·우)으로 주어진 문자열을 재귀적으로 탐색합니다.
• 일치하는 문자열이 발견되면 카운터를 증가시킵니다.
• 첫 번째 시작 문자에 대한 탐색이 끝나면 다음 문자에 대해 동일한 과정을 반복합니다.
• 발견된 일치 횟수들의 합을 계산합니다.
• 최종 결과를 저장한 뒤 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int utilitySearch(string word, int r, int c, string arr[], int maxR, int maxC, int index) {
    int count = 0;
    if (r >= 0 && r <= maxR && c >= 0) {
        if (c <= maxC && word[index] == arr[r][c]) {
            char res = word[index];
            index = index + 1;
            arr[r][c] = 0;
            if (word[index] == 0) {
                count = 1;
            } else {
                count = count + utilitySearch(word, r, c + 1, arr, maxR, maxC, index);
                count = count + utilitySearch(word, r, c - 1, arr, maxR, maxC, index);
                count = count + utilitySearch(word, r + 1, c, arr, maxR, maxC, index);
                count = count + utilitySearch(word, r - 1, c, arr, maxR, maxC, index);
            }
            arr[r][c] = res;
        }
    }
    return count;
}

int findString(string word, int r, int c, string str[], int countR, int countC) {
    int count = 0;
    for (int i = 0; i < countR; ++i) {
        for (int j = 0; j < countC; ++j) {
            count = count + utilitySearch(word, i, j, str, countR - 1, countC - 1, 0);
        }
    }
    return count;
}

int main() {
    string word = "FLOOD";
    string inp[] = {"FPLIOKOD", "FLOODYUT", "YFLOODPU", "FMLOSODT", "FILPOYOD", "FLOOOODE"};
    string str[(sizeof(inp) / sizeof(*inp))];
    for (int i = 0; i < (sizeof(inp) / sizeof(*inp)); ++i) {
        str[i] = inp[i];
    }
    cout << "Count of number of given string in 2D character array: " << findString(word, 0, 0, str, (sizeof(inp) / sizeof(*inp)), str[0].size());
    return 0;
}

이 코드에서 utilitySearch() 함수는 현재 위치의 문자가 찾으려는 단어의 index번째 문자와 일치하는지 확인합니다. 일치하면 해당 칸을 임시로 0으로 표시해 같은 칸이 경로 내에서 중복 사용되지 않도록 한 뒤, 상·하·좌·우 네 방향으로 재귀 호출을 이어갑니다. 단어의 끝에 도달하면 1을 반환해 일치 횟수를 세고, 탐색이 끝나면 원래 문자를 복원하는 백트래킹 방식으로 동작합니다.

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

출력

Count of number of given string in 2D character array: 6