C++ 재귀 함수로 2D 행렬을 2차원 연결 리스트로 변환하는 방법

개요

하나의 행렬(matrix)이 주어졌을 때, 재귀(recursion) 기법을 활용하여 이를 2차원 연결 리스트(2D Linked List)로 변환하는 방법을 알아보겠습니다.

변환된 리스트의 각 노드는 right(오른쪽)와 down(아래) 두 개의 포인터를 가지며, 이를 통해 원본 행렬의 구조를 그대로 유지할 수 있습니다.

예를 들어 입력 행렬이 다음과 같다면,

변환 결과인 2차원 연결 리스트는 다음과 같은 구조를 갖습니다.

알고리즘 접근 방법

이 문제는 다음 단계에 따라 해결할 수 있습니다.

• make_2d_list() 함수를 정의합니다. 이 함수는 행렬 mat, 현재 인덱스 i, j, 그리고 행렬의 크기 m, n을 매개변수로 받습니다.

• 인덱스 i 또는 j가 행렬의 경계를 벗어나면 −

  • NULL을 반환합니다.

• mat[i][j] 값을 가지는 새로운 노드 temp를 생성합니다.

• temp의 right 포인터에는 make_2d_list(mat, i, j + 1, m, n)의 결과를 저장합니다. 즉, 같은 행의 다음 열 노드와 연결됩니다.

• temp의 down 포인터에는 make_2d_list(mat, i + 1, j, m, n)의 결과를 저장합니다. 즉, 다음 행의 같은 열 노드와 연결됩니다.

• temp를 반환합니다.

예제 코드

아래의 C++ 구현 예시를 통해 동작 과정을 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int data;
   TreeNode *right, *down;
   TreeNode(int d){
      data = d;
      right = down = NULL;
   }
};
void show_2d_list(TreeNode* head) {
   TreeNode *right_ptr, *down_ptr = head;
   while (down_ptr) {
      right_ptr = down_ptr;
      while (right_ptr) {
         cout << right_ptr->data << " ";
         right_ptr = right_ptr->right;
      }
      cout << endl;
      down_ptr = down_ptr->down;
   }
}
TreeNode* make_2d_list(int mat[][3], int i, int j, int m, int n) {
   if (i > n - 1 || j > m - 1)
      return NULL;
   TreeNode* temp = new TreeNode(mat[i][j]);
   temp->right = make_2d_list(mat, i, j + 1, m, n);
   temp->down = make_2d_list(mat, i + 1, j, m, n);
   return temp;
}
int main() {
   int m = 3, n = 3;
   int mat[][3] = {
      { 10, 20, 30 },
      { 40, 50, 60 },
      { 70, 80, 90 } };
   TreeNode* head = make_2d_list(mat, 0, 0, m, n);
   show_2d_list(head);
}

입력

{ { 10, 20, 30 },
{ 40, 50, 60 },
{ 70, 80, 90 } }

출력

10 20 30
40 50 60
70 80 90