문제 소개
이 튜토리얼에서는 두 사람이 이동 중 딱 한 번 만날 수 있을 때, 수집할 수 있는 최대 포인트를 구하는 프로그램을 C++로 작성해 보겠습니다.
각 칸에 포인트 값이 담긴 행렬(matrix)이 주어집니다. 두 사람은 서로 다른 모서리에서 출발하여 인접한 칸으로 이동하며, 이동 과정에서 정확히 한 번 만나야 합니다. 우리가 찾아야 하는 것은 두 사람이 만나기까지 수집한 포인트의 합이 최대가 되는 경로입니다.
접근 방식: 동적 계획법(DP)
이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 기본 아이디어는 다음과 같습니다.
- 첫 번째 사람(P1)은 왼쪽 위 모서리에서 출발해 오른쪽 아래 모서리로 이동합니다.
- 두 번째 사람(P2)은 왼쪽 아래 모서리에서 출발해 오른쪽 위 모서리로 이동합니다.
- 행렬 내부의 모든 칸을 '만남 지점' 후보로 삼고, 시작점에서 해당 칸까지, 그리고 해당 칸에서 도착점까지의 최대 포인트를 네 방향에 대해 미리 계산해 둡니다.
- 두 사람의 경로가 만남 지점 외에는 겹치지 않도록, 한 사람은 가로 방향으로, 다른 사람은 세로 방향으로 교차하는 두 가지 경우(op1, op2)를 각각 평가합니다.
이를 위해 네 개의 DP 테이블을 사용합니다.
P1S[i][j]: 첫 번째 사람의 시작점에서 (i, j)까지 이동하며 얻는 최대 포인트P1E[i][j]: (i, j)에서 첫 번째 사람의 도착점까지 이동하며 얻는 최대 포인트P2S[i][j]: 두 번째 사람의 시작점에서 (i, j)까지 이동하며 얻는 최대 포인트P2E[i][j]: (i, j)에서 두 번째 사람의 도착점까지 이동하며 얻는 최대 포인트
모든 후보 칸 (i, j)에 대해 다음 두 가지 조합을 계산하고, 그중 최댓값이 곧 정답이 됩니다.
- op1 : 첫 번째 사람이 좌→우로 통과하고, 두 번째 사람이 하→상으로 통과하는 경우
P1S[i][j-1] + P1E[i][j+1] + P2S[i+1][j] + P2E[i-1][j] - op2 : 첫 번째 사람이 상→하로 통과하고, 두 번째 사람이 좌→우로 통과하는 경우
P1S[i-1][j] + P1E[i+1][j] + P2S[i][j-1] + P2E[i][j+1]
C++ 구현 예제
#include<bits/stdc++.h>
#define M 3
#define N 3
using namespace std;
int findMaxPoints(int A[][M]) {
//storing points
int P1S[M+1][N+1], P1E[M+1][N+1];
memset(P1S, 0, sizeof(P1S));
memset(P1E, 0, sizeof(P1E));
int P2S[M+1][N+1], P2E[M+1][N+1];
memset(P2S, 0, sizeof(P2S));
memset(P2E, 0, sizeof(P2E));
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
P1S[i][j] = max(P1S[i-1][j], P1S[i][j-1]) + A[i-1][j-1];
for (int i=N; i>=1; i--)
for (int j=M; j>=1; j--)
P1E[i][j] = max(P1E[i+1][j], P1E[i][j+1]) + A[i-1][j-1];
for (int i=N; i>=1; i--)
for(int j=1; j<=M; j++)
P2S[i][j] = max(P2S[i+1][j], P2S[i][j-1]) + A[i-1][j-1];
for (int i=1; i<=N; i++)
for (int j=M; j>=1; j--)
P2E[i][j] = max(P2E[i-1][j], P2E[i][j+1]) + A[i-1][j-1];
int ans = 0;
for (int i=2; i<N; i++) {
for (int j=2; j<M; j++) {
int op1 = P1S[i][j-1] + P1E[i][j+1] + P2S[i+1][j] + P2E[i-1][j];
int op2 = P1S[i-1][j] + P1E[i+1][j] + P2S[i][j-1] + P2E[i][j+1];
ans = max(ans, max(op1, op2));
}
}
return ans;
}
int main() {
int A[][M] = {
{100, 100, 100},
{100, 1, 100},
{100, 100, 100}
};
cout << "Max Points : " << findMaxPoints(A);
return 0;
}
실행 결과
Max Points : 800
결과 분석
예제에서 사용된 3×3 행렬은 가장자리가 모두 100이고 중앙만 1입니다. 두 사람이 중앙 칸에서 만나면 거의 포인트를 얻지 못하지만, 중앙을 기준으로 두 경로를 십자(+) 형태로 교차시키면 가장자리의 고득점 칸들을 최대한 활용할 수 있습니다. 그 결과 두 사람은 총 800포인트를 수집할 수 있습니다.
마무리
이 문제는 단순한 최대 합 경로 찾기와 달리, 두 경로가 특정 지점에서 교차해야 한다는 제약 조건이 추가된 변형 문제입니다. 네 개의 DP 테이블로 각 방향별 최댓값을 미리 계산해 두면, 모든 만남 지점 후보를 선형 시간 안에 빠르게 평가할 수 있다는 점이 핵심입니다. 전체 시간 복잡도는 O(N×M), 공간 복잡도 역시 O(N×M)으로 효율적입니다.