C++로 행렬에서 패턴의 방향(가로/세로) 찾기 – KMP 알고리즘 활용

이 문제에서는 문자 값으로 구성된 행렬과 찾고자 하는 패턴이 주어집니다. 우리의 과제는 행렬 안에서 해당 패턴의 방향이 가로(horizontal)인지 세로(vertical)인지를 판별하는 것입니다.

문제 이해를 위한 예시

입력

mat[][] = {
    { r, a, m },
    { a, m, c },
    { w, f, t }
}
패턴 : raw

출력

vertical (세로)

위 예시에서 "raw"라는 패턴은 행렬의 첫 번째 열을 위에서 아래로 읽었을 때(r → a → w) 나타나므로, 패턴의 방향은 세로(vertical)입니다.

해결 접근 방법

가장 단순한 해결책은 행렬의 모든 N개 행에서 길이 M짜리 패턴을 하나씩 직접 검색하는 것입니다. 하지만 이 방법은 비효율적일 수 있으며, 더 효과적인 접근 방식은 KMP(Knuth-Morris-Pratt) 문자열 매칭 알고리즘을 사용하여 행렬의 모든 행과 열에 대해 패턴을 검색하는 것입니다.

KMP 알고리즘은 LPS(Longest Proper Prefix which is also Suffix) 배열을 활용하여 불일치가 발생했을 때 이미 비교한 정보를 재활용하므로, 단순 브루트포스 검색보다 시간 복잡도 면에서 훨씬 유리합니다.

솔루션 구현 예제 코드

#include<bits/stdc++.h>
using namespace std;
#define N 3
void calcLpsValues(char *pat, int M, int *lps) {
    int len = 0;
    int i = 1;
    lps[0] = 0;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i++] = len;
        } else {
            if (len != 0)
                len = lps[len - 1];
            else
                lps[i++] = 0;
        }
    }
}
int searchPattern(char *pat, char *txt) {
    int M = strlen(pat);
    int *lps = (int *)malloc(sizeof(int)*M);
    int j = 0;
    calcLpsValues(pat, M, lps);
    int i = 0;
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == M)
            return 1;
        else if (i < N && pat[j] != txt[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return 0;
}
void findPatternOrientation(char mat[][N], char *pat) {
    char *col = (char*) malloc(N);
    for (int i = 0; i < N; i++) {
        if (searchPattern(pat, mat[i])) {
            cout<<"horizontal";
            return;
        }
        for (int j = 0; j < N; j++)
            col[j] = *(mat[j] + i);
        if (searchPattern(pat, col))
            cout<<"vertical";
    }
}
int main() {
    char mat[N][N] = {{'r', 'a', 'm'},
    {'a', 'm', 'c'},
    {'w', 'f', 't'}};
    char pattern[] = "raw";
    cout<<"The orientation of the pattern in matrix is ";
    findPatternOrientation(mat, pattern);
    return 0;
}

출력 결과

The orientation of the pattern in matrix is vertical

코드 동작 원리

• calcLpsValues(): 패턴에 대한 LPS 배열을 계산합니다. LPS 배열은 각 위치에서 접두사이면서 접미사이기도 한 가장 긴 부분 문자열의 길이를 저장하며, KMP 알고리즘의 핵심 요소입니다.
• searchPattern(): KMP 알고리즘을 이용해 주어진 텍스트(행 또는 열)에서 패턴을 검색하고, 패턴이 발견되면 1을 반환합니다.
• findPatternOrientation(): 먼저 각 행(row)에 대해 가로 방향 검색을 수행하고, 패턴을 찾지 못하면 각 열(column)의 문자들을 임시 배열로 추출하여 세로 방향 검색을 수행합니다.

이처럼 KMP 알고리즘을 행과 열 양방향에 적용하면 O(N × (M + N))의 시간 복잡도로 효율적으로 문제를 해결할 수 있습니다.