이 튜토리얼에서는 행렬의 왼쪽 상단에서 오른쪽 하단까지 이동한 뒤 다시 출발점으로 돌아오는 전체 경로에서 수집할 수 있는 최대 포인트를 구하는 프로그램을 다룹니다.
문제 개요
주어지는 행렬은 다음 세 가지 문자로 구성됩니다.
#: 지나갈 수 없는 막힌 경로*: 수집할 수 있는 포인트.: 자유롭게 통과할 수 있는 경로
목표는 한쪽 구석에서 반대편 구석으로 이동(오른쪽·아래 방향만 허용)한 후, 되돌아오는 길(왼쪽·위 방향만 허용)까지 합쳐 가장 많은 포인트를 수집하는 것입니다.
핵심 아이디어
왕복 경로를 그대로 시뮬레이션하기보다는, 두 사람이 동시에 왼쪽 상단에서 오른쪽 하단으로 이동한다고 가정하면 문제가 단순해집니다. 두 경로의 길이가 항상 같으므로 각 단계마다 row1 + col1 == row2 + col2가 성립합니다. 따라서 col2는 나머지 세 변수로 유도할 수 있어, 메모이제이션 차원을 크게 줄일 수 있습니다. 또한 두 사람이 같은 칸에 도착하면 포인트는 한 번만 계산해야 합니다.
C++ 구현 예제
#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;
// 현재 위치의 포인트 계산 (같은 칸이면 중복 제외)
int cost(char grid[][M], int row1, int col1, int row2, int col2) {
if (row1 == row2 && col1 == col2) {
if (grid[row1][col1] == '*')
return 1;
return 0;
}
int ans = 0;
if (grid[row1][col1] == '*')
ans++;
if (grid[row2][col2] == '*')
ans++;
return ans;
}
// 최대 포인트를 재귀적으로 계산하는 함수
int solve(int n, int m, char grid[][M], int dp[MAX][MAX][MAX], int row1, int col1, int row2) {
int col2 = (row1 + col1) - (row2);
if (row1 == n - 1 && col1 == m - 1 && row2 == n - 1 && col2 == m - 1)
return 0;
if (row1 >= n || col1 >= m || row2 >= n || col2 >= m)
return -1 * inf;
if (dp[row1][col1][row2] != -1)
return dp[row1][col1][row2];
int ch1 = -1 * inf, ch2 = -1 * inf;
int ch3 = -1 * inf, ch4 = -1 * inf;
// 첫 번째: 아래, 두 번째: 아래
if (grid[row1][col1 + 1] != '#' &&
grid[row2 + 1][col2] != '#')
ch1 = cost(grid, row1, col1 + 1, row2 + 1, col2) + solve(n, m, grid, dp, row1, col1 + 1, row2 + 1);
// 첫 번째: 아래, 두 번째: 오른쪽
if (grid[row1][col1 + 1] != '#' &&
grid[row2][col2 + 1] != '#')
ch2 = cost(grid, row1, col1 + 1, row2, col2 + 1) + solve(n, m, grid, dp, row1, col1 + 1, row2);
// 첫 번째: 오른쪽, 두 번째: 오른쪽
if (grid[row1 + 1][col1] != '#' &&
grid[row2][col2 + 1] != '#')
ch3 = cost(grid, row1 + 1, col1, row2, col2 + 1) + solve(n, m, grid, dp, row1 + 1, col1, row2);
// 첫 번째: 오른쪽, 두 번째: 아래
if (grid[row1 + 1][col1] != '#' &&
grid[row2 + 1][col2] != '#')
ch4 = cost(grid, row1 + 1, col1, row2 + 1, col2) + solve(n, m, grid, dp, row1 + 1, col1, row2 + 1);
return dp[row1][col1][row2] = max({ch1, ch2, ch3, ch4});
}
// 전체 실행을 감싸는 래퍼 함수
int wrapper(int n, int m, char grid[N][M]) {
int ans = 0;
int dp[MAX][MAX][MAX];
memset(dp, -1, sizeof dp);
// 시작점과 끝점이 막혀 있으면 수집 불가
if (grid[n - 1][m - 1] == '#' || grid[0][0] == '#')
ans = -1 * inf;
// 시작점과 끝점의 포인트는 미리 처리 후 '.'로 변경
if (grid[0][0] == '*')
ans++;
grid[0][0] = '.';
if (grid[n - 1][m - 1] == '*')
ans++;
grid[n - 1][m - 1] = '.';
ans += solve(n, m, grid, dp, 0, 0, 0);
return max(ans, 0);
}
int main() {
int n = 5, m = 5;
char grid[N][M] = {
{ '.', '*', '.', '*', '.' },
{ '*', '#', '#', '#', '.' },
{ '*', '.', '*', '.', '*' },
{ '.', '#', '#', '#', '*' },
{ '.', '*', '.', '*', '.' }
};
cout << wrapper(n, m, grid) << endl;
return 0;
}
출력 결과
8
코드 설명
solve() 함수는 네 가지 이동 조합(각각의 사람이 오른쪽 또는 아래로 이동하는 경우)을 모두 탐색하며, 막힌 경로(#)는 사전에 차단합니다. 이미 계산된 상태는 3차원 DP 배열 dp[row1][col1][row2]에 저장되어 중복 연산을 방지하므로, 전체 시간 복잡도는 O(N × M × N)으로 효율적입니다. wrapper() 함수는 시작점과 끝점의 포인트를 미리 더한 뒤 해당 칸을 .으로 바꿔 중복 계산을 막습니다.