문제 개요
이 문제에서는 소문자 알파벳으로만 구성된 행렬(matrix)이 주어지며, 행렬의 왼쪽 위(좌상단) 칸에서 오른쪽 아래(우하단) 칸으로 이동하면서 만들 수 있는 모든 경로 중, 문자열이 회문(palindrome)이 되는 경로를 모두 출력해야 합니다.
허용되는 이동은 오른쪽과 아래쪽 두 방향뿐이며, 대각선 이동은 허용되지 않습니다.
문제 예시
예제를 통해 문제를 이해해 보겠습니다.
입력: matrix[][] = {
{"xxxy",
"yxxx",
"xyyx"}
출력: xxxxxx , xxxxxx , xyxxyx풀이 설명
왼쪽 위에서 오른쪽 아래까지 도달할 수 있는 모든 유효한 이동 경로를 각 칸의 인덱스를 기준으로 나타내면 다음과 같습니다.
i00 -> i01 -> i02 -> i03 -> i13 -> i23 = xxxyxx i00 -> i01 -> i11 -> i12 -> i13 -> i23 = xxxxxx . . . i00 -> i10 -> i20 -> i21 -> i22 -> i23 = xyxyyx
가능한 모든 결과 문자열 중에서 우리가 원하는 것은 회문이 되는 경로입니다. 즉, 앞에서 읽으나 뒤에서 읽으나 같은 문자열이 만들어지는 경로만 골라내면 됩니다.
i00 -> i01 -> i11 -> i12 -> i13 -> i23 = xxxxxx i00 -> i01 -> i02 -> i12 -> i13 -> i23 = xxxxxx i00 -> i10 -> i11 -> i12 -> i22 -> i23 = xyxxyx
이 설명 자체가 곧 문제 해결의 핵심 아이디어입니다. 왼쪽 위에서 오른쪽 아래까지의 모든 경로를 탐색하고, 그중 회문이 되는 경로만 골라 출력하면 됩니다.
C++ 구현 예제
아래 예제 코드는 재귀 호출을 통해 모든 경로를 탐색하고 회문 여부를 검사하는 방식으로 문제를 해결합니다.
#include<iostream>
using namespace std;
#define N 4
int printPalindrome(string str){
int len = str.length() / 2;
for (int i = 0; i < len; i++) {
if (str[i] != str[str.length() - i - 1])
return 0;
}
cout<<str<<endl;
}
void findPath(string str, char a[][N], int i, int j, int m, int n) {
if (j < m - 1 || i < n - 1) {
if (i < n - 1)
findPath(str + a[i][j], a, i + 1, j, m, n);
if (j < m - 1)
findPath(str + a[i][j], a, i, j + 1, m, n);
} else {
str = str + a[n - 1][m - 1];
printPalindrome(str) ;
}
}
int main() {
char matrix[][N] = {
{ 'x', 'y', 'x', 'y' },
{ 'y', 'x', 'x', 'y' },
{ 'y', 'x', 'y', 'x' }
};
string str = "";
cout<<"Palimdromic path are : ";
findPath(str, matrix, 0, 0, 4, 3);
return 0;
}코드 동작 원리
- findPath 함수: 현재 위치에서 아래쪽 또는 오른쪽으로 이동하면서 재귀적으로 모든 경로를 탐색합니다. 이동할 때마다 해당 칸의 문자를 경로 문자열에 추가합니다.
- 경로 완성: 행렬의 마지막 칸에 도달하면 지금까지 모은 문자열에 마지막 문자를 덧붙여 하나의 완전한 경로 문자열을 만듭니다.
- printPalindrome 함수: 완성된 문자열의 앞부분과 뒷부분을 순서대로 비교하여 회문 여부를 검사하고, 회문일 경우에만 화면에 출력합니다.
실행 결과
Palimdromic path are : xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx
이처럼 재귀적 깊이 우선 탐색(DFS) 방식을 활용하면 행렬 내 모든 이동 경로를 체계적으로 확인할 수 있으며, 각 경로가 완성될 때마다 회문 검사만 수행하면 원하는 답을 손쉽게 얻을 수 있습니다.