C++에서 2D 행렬을 2D 연결 리스트로 변환하기 (반복적 접근 방식)

문제 개요

하나의 행렬(matrix)이 주어졌을 때, 반복적(iterative) 접근 방식을 사용하여 이를 2차원 연결 리스트로 변환해야 합니다. 이 리스트의 각 노드는 right(오른쪽)와 down(아래쪽) 두 개의 포인터를 가지며, 행렬의 구조를 그대로 유지합니다.

예를 들어, 입력 행렬이 다음과 같다고 가정해 보겠습니다.

이 행렬을 2D 연결 리스트로 변환하면, 같은 행에 있는 노드들은 right 포인터로, 같은 열에 있는 노드들은 down 포인터로 연결됩니다. 즉, 10 → 20 → 30은 오른쪽 방향으로, 10 → 40 → 70은 아래쪽 방향으로 연결되는 구조입니다.

해결 알고리즘

이 문제는 다음 단계를 통해 해결할 수 있습니다.

1. real_head를 NULL로 초기화합니다. 이 변수가 최종적으로 반환될 전체 리스트의 시작점이 됩니다.
2. 크기가 m인 배열 head_arr를 선언하여 각 행의 첫 번째 노드 주소를 저장합니다.
3. i = 0부터 m 미만까지 반복합니다.
   • head_arr[i]를 NULL로 초기화합니다.
   • j = 0부터 n 미만까지 반복하면서 값이 mat[i][j]인 새 노드 p를 생성합니다.
   • real_head가 NULL이면 p를 할당합니다(전체 리스트의 첫 번째 노드).
   • head_arr[i]가 NULL이면 p를 할당하고, 그렇지 않으면 앞서 저장한 right_ptr의 right에 p를 연결합니다.
   • right_ptr을 p로 갱신합니다.
4. 모든 행의 가로 연결이 완료되면, i = 0부터 m-2까지 반복하면서 인접한 두 행을 세로로 연결합니다.
   • p = head_arr[i], q = head_arr[i+1]로 설정합니다.
   • p와 q가 모두 NULL이 아닌 동안 p의 down을 q로 지정하고, 두 포인터를 각자의 right 노드로 이동시킵니다.
5. real_head를 반환합니다.

C++ 구현 예제

아래는 위 알고리즘을 그대로 구현한 전체 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 m, int n) {
    TreeNode* real_head = NULL;
    TreeNode* head_arr[m];
    TreeNode *right_ptr, *p;
    for (int i = 0; i < m; i++) {
        head_arr[i] = NULL;
        for (int j = 0; j < n; j++) {
            p = new TreeNode(mat[i][j]);
            if (!real_head)
                real_head = p;
            if (!head_arr[i])
                head_arr[i] = p;
            else
                right_ptr->right = p;
            right_ptr = p;
        }
    }
    for (int i = 0; i < m - 1; i++) {
        TreeNode *p = head_arr[i], *q = head_arr[i + 1];
        while (p && q) {
            p->down = q;
            p = p->right;
            q = q->right;
        }
    }
    return real_head;
}
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, m, n);
    show_2d_list(head);
}

입력

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

출력

10 20 30
40 50 60
70 80 90

복잡도 분석

행렬의 모든 원소를 정확히 한 번씩 방문하므로 시간 복잡도는 O(m×n)입니다. 또한 각 원소마다 새로운 노드를 동적으로 할당하므로 공간 복잡도 역시 O(m×n)입니다.