주어진 시작 문자에서 출발하는 가장 긴 연속 경로 찾기

문제 개요

서로 다른 문자들로 구성된 행렬이 주어집니다. 하나의 문자에서 시작하여, 현재 문자보다 알파벳 순서상 정확히 한 단계 뒤에 오는 문자(예: 'a' → 'b', 'b' → 'c')를 따라 인접 칸으로 이동할 때 만들 수 있는 가장 긴 연속 경로의 길이를 구하는 것이 목표입니다.

이동은 상하좌우뿐 아니라 대각선 방향을 포함한 총 8방향의 인접 칸으로 가능하며, 각 이동 시 문자는 반드시 연속되어야 합니다.

해결 접근 방법

이 문제는 깊이 우선 탐색(DFS)으로 해결할 수 있습니다. 그러나 DFS를 수행하는 과정에서 동일한 부분 문제(subproblem)가 여러 번 중복해서 발생하게 됩니다. 이러한 중복 계산을 피하기 위해 동적 계획법(Dynamic Programming), 즉 메모이제이션 기법을 함께 사용합니다. 이미 계산된 위치의 최장 경로 길이를 배열에 저장해 두었다가 재사용하는 방식입니다.

입력과 출력

Input:
위와 같은 문자 행렬과 시작 지점. 여기서는 시작 지점이 e.
Output:
Enter Starting Point (a-i): e
Maximum consecutive path: 5

알고리즘

findLongestLen(i, j, prev)

입력: 위치 i, j와 이전 문자(prev)
출력: 해당 위치에서 시작하는 최장 경로의 길이

Begin
    if (i, j)가 유효하지 않거나 prev와 matrix[i,j]가 연속되지 않으면
        return 0
    if longestPath[i, j]가 이미 채워져 있으면
        return longestPath[i, j]
    len := 0

    8개의 인접 칸 k에 대해 반복:
        len := len과 (1 + findLongestLen(i + x[k], j + y[k], matrix[i, j])) 중 큰 값
    done

    longestPath[i, j] := len
    return len
End

getLen(start)

입력: 시작 문자
출력: 전체 행렬에서 구할 수 있는 최대 경로 길이

Begin
    행렬의 모든 행 r에 대해 반복:
        모든 열 c에 대해 반복:
            if matrix[i, j] = start 이면
                8개의 인접 칸 k에 대해 반복:
                    len := len과 (1 + findLongestLen(i + x[k], j + y[k], start)) 중 큰 값
                done
    done
    return len
End

C++ 구현 예제

#include<iostream>
#define ROW 3
#define COL 3
using namespace std;

// 인접 칸 재귀 호출을 위한 방향 벡터
int x[] = {0, 1, 1, -1, 1, 0, -1, -1};
int y[] = {1, 0, 1, 1, -1, -1, 0, -1};
int longestPath[ROW][COL];

char mat[ROW][COL] = {
    {'a','c','d'},
    {'h','b','a'},
    {'i','g','f'}
};

int max(int a, int b) {
    return (a>b)?a:b;
}

bool isvalid(int i, int j) {
    if (i < 0 || j < 0 || i >= ROW || j >= COL)   // i, j가 범위를 벗어나는 경우
        return false;
    return true;
}

bool isadjacent(char previous, char current) {
    return ((current - previous) == 1);   // 현재 문자와 이전 문자가 연속되는지 확인
}

int findLongestLen(int i, int j, char prev) {
    if (!isvalid(i, j) || !isadjacent(prev, mat[i][j]))   // 범위 밖이거나 연속되지 않는 경우
        return 0;

    if (longestPath[i][j] != -1)
        return longestPath[i][j];   // 이미 해결된 부분 문제는 저장된 값 반환

    int len = 0;   // 결과를 0으로 초기화

    for (int k=0; k<8; k++)   // 8방향으로 재귀적으로 최장 경로 탐색
        len = max(len, 1 + findLongestLen(i + x[k], j + y[k], mat[i][j]));
    return longestPath[i][j] = len;   // 계산 결과를 저장하고 반환
}

int getLen(char start) {
    for(int i = 0; i<ROW; i++)
        for(int j = 0; j<COL; j++)
            longestPath[i][j] = -1;   // 모든 값을 -1로 초기화

    int len = 0;

    for (int i=0; i<ROW; i++) {
        for (int j=0; j<COL; j++) {   // 가능한 모든 시작 지점 검사
            if (mat[i][j] == start) {
                for (int k=0; k<8; k++)   // 8개의 인접 칸에 대해 탐색
                    len = max(len, 1 + findLongestLen(i + x[k], j + y[k], start));
            }
        }
    }
    return len;
}

int main() {
    char start;
    cout << "Enter Starting Point (a-i): "; cin >> start;
    cout << "Maximum consecutive path: " << getLen(start);
    return 0;
}

실행 결과

Enter Starting Point (a-i): e
Maximum consecutive path: 5

위 예제에서 시작 문자 'e'로부터 'e → f → g → h → i'로 이어지는 경로가 만들어지며, 최장 연속 경로의 길이는 5가 됩니다. 이처럼 DFS와 메모이제이션을 결합하면 중복 계산 없이 효율적으로 최장 연속 경로를 구할 수 있습니다.