C++로 최대 길이의 뱀 시퀀스(Snake Sequence) 찾기

개념

주어진 숫자 격자(grid)에서 최대 길이의 뱀 시퀀스(Snake Sequence)를 찾아 화면에 출력하는 것이 목표입니다. 만약 최대 길이를 가지는 뱀 시퀀스가 여러 개 존재한다면, 그중 아무거나 하나만 출력하면 됩니다.

여기서 뱀 시퀀스란 격자 안에서 서로 인접한 숫자들로 이루어진 경로를 말하며, 각 숫자 기준으로 오른쪽 또는 아래에 있는 숫자가 현재 값보다 +1 또는 -1 차이가 나야 합니다. 즉, 현재 위치가 (a, b)라면 오른쪽 칸 (a, b+1)이 ±1 차이일 때 오른쪽으로 이동하거나, 아래 칸 (a+1, b)이 ±1 차이일 때 아래로 이동할 수 있습니다.

예를 들어 다음과 같은 격자가 있다고 가정해 보겠습니다.

10, 7, 6, 3
9, 8, 7, 6
8, 4, 2, 7
2, 2, 2, 8

위 격자에서 최대 길이의 뱀 시퀀스는 다음과 같습니다.

(10, 9, 8, 7, 6, 7, 8)

아래 그림은 가능한 모든 경로를 보여줍니다.

10   7  → 6    3
↓    ↓    ↓
9 →  8 →  7 →  6
↓    ↓
8    4    2    7
↓
2    2    2    8

풀이 방법

이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. 행렬의 각 셀에 대해 '현재 셀에서 끝나는 뱀 시퀀스의 최대 길이'를 저장합니다. 그러면 전체 테이블에서 가장 큰 값을 가지는 셀이 곧 최대 길이 뱀 시퀀스의 끝(꼬리)이 됩니다.

뱀의 전체 경로를 출력하려면 꼬리에서부터 머리까지 역추적(backtracking)해야 합니다. T[a][b]를 셀 (a, b)에서 끝나는 뱀 시퀀스의 최대 길이라고 하고, 주어진 행렬을 M이라 할 때 점화식은 다음과 같습니다.

T[0][0] = 0
T[a][b] = max(T[a][b], T[a][b – 1] + 1)  if M[a][b] = M[a][b – 1] ± 1
T[a][b] = max(T[a][b], T[a – 1][b] + 1)  if M[a][b] = M[a – 1][b] ± 1

C++ 구현 예제

// 최대 길이의 뱀 시퀀스를 찾아 출력하는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
#define M 4
#define N 4

struct Point {
    int X, Y;
};

// 최대 길이 뱀 시퀀스의 경로를 찾는 함수
// (a, b)는 뱀의 꼬리 위치에 해당
list<Point> findPath(int grid1[M][N], int mat1[M][N], int a, int b) {
    list<Point> path1;
    Point pt1 = {a, b};
    path1.push_front(pt1);

    while (grid1[a][b] != 0) {
        // 위쪽 셀 확인
        if (a > 0 && grid1[a][b] - 1 == grid1[a - 1][b]) {
            pt1 = {a - 1, b};
            path1.push_front(pt1);
            a--;
        }
        // 왼쪽 셀 확인
        else if (b > 0 && grid1[a][b] - 1 == grid1[a][b - 1]) {
            pt1 = {a, b - 1};
            path1.push_front(pt1);
            b--;
        }
    }
    return path1;
}

// 최대 길이 뱀 시퀀스를 찾는 함수
void findSnakeSequence(int mat1[M][N]) {
    // 부분 문제의 결과를 저장하는 테이블
    int lookup1[M][N];

    // 0으로 초기화
    memset(lookup1, 0, sizeof lookup1);

    // 뱀 시퀀스의 최대 길이 저장
    int max_len1 = 0;

    // 뱀의 꼬리 좌표 저장
    int max_row1 = 0;
    int max_col1 = 0;

    // 상향식(bottom-up)으로 테이블 채우기
    for (int a = 0; a < M; a++) {
        for (int b = 0; b < N; b++) {
            // (0, 0) 셀은 제외
            if (a || b) {
                // 위쪽 셀 검사
                if (a > 0 && abs(mat1[a - 1][b] - mat1[a][b]) == 1) {
                    lookup1[a][b] = max(lookup1[a][b],
                                        lookup1[a - 1][b] + 1);
                    if (max_len1 < lookup1[a][b]) {
                        max_len1 = lookup1[a][b];
                        max_row1 = a, max_col1 = b;
                    }
                }
                // 왼쪽 셀 검사
                if (b > 0 && abs(mat1[a][b - 1] - mat1[a][b]) == 1) {
                    lookup1[a][b] = max(lookup1[a][b],
                                        lookup1[a][b - 1] + 1);
                    if (max_len1 < lookup1[a][b]) {
                        max_len1 = lookup1[a][b];
                        max_row1 = a, max_col1 = b;
                    }
                }
            }
        }
    }

    cout << "Maximum length of Snake sequence is: "
         << max_len1 << endl;

    // 최대 길이 뱀 시퀀스의 경로 탐색
    list<Point> path1 = findPath(lookup1, mat1, max_row1, max_col1);

    cout << "Snake sequence is:";
    for (auto it = path1.begin(); it != path1.end(); it++)
        cout << endl << mat1[it->X][it->Y]
             << " (" << it->X << ", " << it->Y << ")";
}

// 드라이버 코드
int main() {
    int mat1[M][N] = {{10, 7, 6, 3},
                      {9, 8, 7, 6},
                      {8, 4, 2, 7},
                      {2, 2, 2, 8}};
    findSnakeSequence(mat1);
    return 0;
}

실행 결과

Maximum length of Snake sequence is: 6
Snake sequence is:
10 (0, 0)
9 (1, 0)
8 (1, 1)
7 (1, 2)
6 (1, 3)
7 (2, 3)
8 (3, 3)