C++로 시작 문자부터 가장 긴 연속 경로의 길이 구하기

서로 다른 문자들로 구성된 행렬이 주어졌을 때, 하나의 시작 문자에서 출발하여 현재 문자보다 알파벳 순서상 1만큼 큰 문자들을 따라 이동하며 만들 수 있는 가장 긴 연속 경로의 길이를 구하는 문제입니다. 예를 들어 'e'에서 출발했다면 'f', 'g', 'h', 'i'처럼 연속되는 문자만 거치며 진행할 수 있습니다.

위 그림은 'E'에서 시작하는 경우의 예시입니다.

문제 해결 접근 방식

가장 긴 경로를 찾기 위해 깊이 우선 탐색(Depth First Search, DFS) 알고리즘을 사용합니다. DFS를 수행하는 도중에는 동일한 부분 문제(subproblem)가 여러 번 반복해서 나타날 수 있습니다. 이러한 부분 문제를 매번 다시 계산하는 비효율을 없애기 위해 동적 계획법(Dynamic Programming), 즉 메모이제이션 기법을 함께 적용합니다. 한 번 계산한 셀의 최장 경로 길이는 별도의 2차원 배열에 저장해 두었다가 재활용하는 방식입니다.

알고리즘의 주요 단계

행렬 전체를 훑으며 시작 문자와 일치하는 셀을 찾습니다.
각 셀에서 상하좌우와 대각선을 포함한 8개 방향으로의 이동 가능 여부를 검사합니다.
이동할 셀의 문자가 현재 문자보다 정확히 1만큼 클 때만 경로를 확장합니다.
DFS로 각 방향의 경로 길이를 재귀적으로 계산하되, 이미 계산된 값은 캐시에서 가져옵니다.
모든 시작 후보 셀에 대해 계산을 마친 뒤 최댓값을 반환합니다.

C++ 구현 예제

#include<iostream>
#define ROW 3
#define COL 3
using namespace std;
// 인접 셀을 재귀적으로 탐색하기 위한 8방향 좌표 배열
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와 메모이제이션을 결합하면 중복 계산을 줄여 효율적으로 최장 연속 경로를 구할 수 있습니다.