C++로 풀어보는 이진 행렬 경로의 최대 10진수 값 구하기

이 글에서는 주어진 정사각형 이진 행렬에서 왼쪽 위 칸([0][0])에서 출발하여 오른쪽 아래 칸([n-1][n-1])에 도달하는 경로를 따라 만들 수 있는 최대 10진수 값을 구하는 방법을 알아봅니다.

경로를 따라 이동할 때는 오른쪽([i][j+1]) 또는 아래쪽([i+1][j])으로만 움직일 수 있으며, 최종 정수 값은 지나간 칸들의 비트 값을 이용해 계산됩니다.

문제 이해하기

예제를 통해 문제를 자세히 살펴보겠습니다.

입력

m = {
    {1, 1, 1, 1},
    {0, 0, 1, 0},
    {1, 0, 1, 1},
    {0, 1, 1, 1}
}

출력

설명

선택한 경로는 다음과 같습니다.

[0, 0] → [0, 1] → [0, 2] → [1, 2] → [2, 2] → [3, 2] → [3, 3]

이 경로에 포함된 모든 칸의 값이 1이므로, 각 비트가 나타내는 2의 거듭제곱을 모두 더하면 다음과 같은 결과가 나옵니다.

= 1×(2⁰) + 1×(2¹) + 1×(2²) + 1×(2³) + 1×(2⁴) + 1×(2⁵) + 1×(2⁶)
= 1 + 2 + 4 + 8 + 16 + 32 + 64
= 127

다른 예제

m = {
    {1, 0, 1, 1},
    {0, 0, 1, 0},
    {1, 0, 0, 1},
    {0, 1, 1, 1}
}

이 경우의 출력 결과는 109입니다.

접근 방법

#define을 사용해 정사각형 행렬의 한 변의 크기를 미리 정의합니다.
main() 함수에서 2차원 배열 int m[][4]를 선언해 행렬을 저장한 뒤, Max(m, 0, 0, 0)을 호출합니다.
Max() 함수에서는 먼저 i >= side 또는 j >= side 인지 검사합니다. 조건이 참이면 현재 위치가 행렬의 경계를 벗어난 것이므로 0을 반환합니다.
새로운 변수 int ans를 만들고, ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1))로 초기화합니다. 즉, 오른쪽과 아래쪽 두 방향 중 더 큰 값을 선택합니다.
그다음 m[i][j] == 1인지 확인하고, 참이라면 pow(2, pw) + ans를 반환합니다.
값이 0이라면 ans만 그대로 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
#define side 4
// pw는 2의 거듭제곱 지수
int Max(int m[][side], int i, int j, int pw){
    // 행렬 범위를 벗어난 경우
    if (i >= side || j >= side)
        return 0;
    int ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1));
    if (m[i][j] == 1)
        return pow(2, pw) + ans;
    else
        return ans;
}
// 메인 함수
int main(){
    int m[][4] = {{1, 1, 1, 1},{0, 0, 1, 0},{1, 0, 1, 1},{0, 1, 1, 1}};
    cout << Max(m, 0, 0, 0);
    return 0;
}

출력

복잡도 분석

위 구현은 가능한 모든 경로를 재귀적으로 탐색하는 브루트포스 방식이므로, n×n 행렬에서 경로의 수가 대략 C(2n−2, n−1)개에 달해 시간 복잡도가 지수적으로 증가합니다. 따라서 행렬의 크기가 커지면 실행 시간이 빠르게 늘어날 수 있습니다.

메모이제이션을 적용해 (i, j) 좌표별 결과를 캐싱하면 상태의 수가 O(n²)로 줄어들어 훨씬 효율적으로 문제를 해결할 수 있습니다. 실전에서는 동적 계획법(DP)을 활용한 최적화를 함께 고려하는 것이 좋습니다.