[프로그래머스] 길 찾기 게임 - 구조체에 대한 이해

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

오늘 풀어본 문제는 길 찾기 게임이다.

 

이 문제는

1. 주어진 2차원 좌표 배열을 이진 트리로 변환

2. 변환한 트리를 전위 탐색, 후위 탐색

하는 것이 핵심인 문제이다.

 

여기서 좀 더 세부적으로는, 이진 트리 자료 구조를 구현하기 위해서 Node 구조체를 만들어 사용해야 했다.

struct Node {
    Node(int id, int x, int y) {
        this->id = id;
        this->x = x;
        this->y = y;
        left = nullptr;
        right = nullptr;
    }
    int id;
    int x;
    int y;
    Node* left;
    Node* right;
};

구조체를 많이 사용해본 적이 없었기에, 함수나 반복문 스코프에서 사용될 때의 생명주기에 대해 모르는 게 많아 문법을 고치는 데 오래 걸렸다. 그래서 앞으로도 기억해두면 좋을 포인트들을 정리해보겠다.

 

1. 지역 변수 구조체는 스코프가 끝나면 소멸된다.

 

반복문 스코프에서 선언된 변수는 반복문이 끝나면 스택 메모리가 해제된다. 이는 구조체 지역 변수에도 동일하게 적용된다. insertNode 함수에서 rootNode에 아무리 열심히 자식 노드 포인터에 nextNode를 연결해도, 한 번의 반복문이 끝나면 메모리가 해제되어 있기 때문에 rootNode는 이미 사라진 지역 변수의 주소를 가리키게 된다.

이렇게 이미 해제된 메모리를 가리키는 포인터를 dangling pointer라고 부른다.

// ❌ 잘못된 코드
void solution() {
    vector<Node> nodes;
    ...
    // 다음에 삽입할 노드 찾기
    // 삽입되지 않은 노드 중, y 값이 가장 큰 노드
    while (nodes.size() > 0) {
        Node nextNode = nodes.back();
        nodes.pop_back();

        insertNode(&rootNode, &nextNode); // 햠수가 끝나면 nextNode가 소멸됨. dangling pointer 발생
    }
	...
}

 

Q. 함수에서 선언한 객체를 함수가 끝나도 사용하고 싶은데, 이럴 땐 어떡할까?

-> new를 이용하여 힙에 동적 메모리를 할당한다. 그러면 메모리를 직접 해제하기 전까지 객체를 사용할 수 있다.

 

// ✅ 올바른 코드
while (nodes.size() > 0) {
    Node temp = nodes.back();
    Node* nextNode = new Node(temp.id, temp.x, temp.y); // 동적 메모리 할당!
    nodes.pop_back();

    insertNode(&rootNode, nextNode); // 함수가 끝나도 생성한 nextNode가 유지됨
}

 

2. 벡터에서 구조체를 push_back() 하면 복사되어 들어간다.

 

나같은 경우, 노드들을 오름차순 정렬하기 위해 구조체 벡터를 만들었다.

 

이때, for문 스코프에서 지역 변수 구조체 Node를 생성하고, vector<Node>에 넣는 건 괜찮을까??

for (int i = 0; i < nodeinfo.size(); i++) {
    const vector<int>& node = nodeinfo[i];
    Node newNode(i + 1, node[0], node[1]);
    nodes.push_back(newNode);
}

이건 괜찮다. push_back을 할 때 노드를 복사해서 저장하기 때문이다.

하지만 1번과 같은 이유로

nodes.push_back(&newNode)

는 dangling pointer 이슈가 일어나므로 작성하면 안 된다. 지역 변수의 주소를 전달했지만 이는 반복문 한 바퀴가 끝나면 이 지역 변수는 사라지기 때문이다.

 

3. 벡터에서 구조체를 back() 하면 마지막 원소의 참조를 반환한다.

 

1. Node a = nodes.back() // 마지막 Node 자체를 복사한다.
2. Node &a = nodes.back() // 마지막 Node 자체를 참조한다. 원본의 별명이라고 볼 수 있음.
3. Node *a = &nodes.back() // 마지막 Node의 주소이다.

 

벡터의 마지막 원소를 반환하는 back() 함수를 호출하면 해당 원소의 참조를 반환하는데, 어떤 변수에 받느냐에 따라 역할이 완전히 달라진다.

내가 짠 코드의 경우에는, 저렇게 back()을 호출한 뒤 nodes.pop_back()을 수행해야 했다. 이 경우 2번과 3번은 원본이 사라져버리기 때문에 dangling pointer가 된다.

즉, 뽑아낸 원소를 나중에 사용할 거라면, 1번과 같이 새로운 객체를 만든 뒤, 내용을 복사해서 사용해야 한다.

 

2번의 참조 변수와 3번의 포인터 변수에 대한 설명을 보충하자면,

둘 다 원본 수정이 가능하지만 사용법과 용도가 다르다.

 

사용법의 경우,

참조 변수는 구조체 자체라고 볼 수 있으므로, a.x로 접근하고,

포인터 변수는 a->x로 접근한다.

 

Q. 그러면 둘 다 원본을 다루는데, 왜 굳이 구분해놓은 걸까?

-> 참조는 반드시 존재하는 객체를 원본 그대로 다루고 싶을 때 사용하고,

포인터는 객체가 nullptr일 수도 있기 때문에 nullptr을 허용하는 주소를 이용한다.

 

진짜 마지막 여담인데, sort의 compare 함수의 매개변수에서 참조 변수(&)를 사용하는 이유도 이와 직결된다.

sort(nodes.begin(), nodes.end(), compare);

// y 좌표 오름차순 정렬
bool compare(const Node& A, const Node& B) {
    return A.y < B.y;
}

sort 함수를 호출하면 compare(nodes[0], nodes[1]);

이런 형태로 호출하게 되는데, compare 함수에서 이 객체를 복사하지 않고 원본 그대로를 가져와 사용하기 위함이다.

 

만약 vector<Node> nodes가 아닌 vector<Node*> nodes였다면, 이때는 포인터의 참조를 사용하는 것도 가능하지만,

포인터 자체를 복사하는 것은 비용이 크지 않기 때문에 매개 변수에 포인터 변수를 사용하는 것이 쉽고 간단하다.

 

4. 전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    Node(int id, int x, int y) {
        this->id = id;
        this->x = x;
        this->y = y;
        left = nullptr;
        right = nullptr;
    }
    int id;
    int x;
    int y;
    Node* left;
    Node* right;
};

void preOrder(const Node* cur, vector<int>* order) {
    // 자기 자신 탐색
    order->push_back(cur->id);

    // Left Subtree 순회
    if (cur->left != nullptr) {
        preOrder(cur->left, order);
    }

    // Right Subtree 순회
    if (cur->right != nullptr) {
        preOrder(cur->right, order);
    }

    return;
}

void postOrder(const Node* cur, vector<int>* order) {
    // Left Subtree 순회
    if (cur->left != nullptr) {
        postOrder(cur->left, order);
    }

    // Right Subtree 순회
    if (cur->right != nullptr) {
        postOrder(cur->right, order);
    }

    // 자기 자신 탐색
    order->push_back(cur->id);

    return;
}

// y 좌표 오름차순 정렬
bool compare(const Node& A, const Node& B) {
    return A.y < B.y;
}

// 이진 트리에 노드 삽입
void insertNode(Node* ref, Node* cur) {
    if (cur->x < ref->x) {
        if (ref->left == nullptr) {
            ref->left = cur;
            return;
        }
        else {
            insertNode(ref->left, cur);
        }
    }
    else {
        if (ref->right == nullptr) {
            ref->right = cur;
            return;
        }
        else {
            insertNode(ref->right, cur);
        }
    }
}

void deleteTree(Node* node) {
    if (node == nullptr) return;

    deleteTree(node->left);
    deleteTree(node->right);

    delete node;
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<Node> nodes;

    for (int i = 0; i < nodeinfo.size(); i++) {
        const vector<int>& node = nodeinfo[i];
        Node newNode(i + 1, node[0], node[1]);
        nodes.push_back(newNode);
    }

    // 구조체 벡터 배열을 오름차순으로 정렬
    sort(nodes.begin(), nodes.end(), compare);

    // 루트 노드 찾기
    Node rootNode = nodes.back();
    nodes.pop_back();
    
    // 다음에 삽입할 노드 찾기
    // 삽입되지 않은 노드 중, y 값이 가장 큰 노드
    while (nodes.size() > 0) {
        Node temp = nodes.back();
        Node* nextNode = new Node(temp.id, temp.x, temp.y);
        nodes.pop_back();

        insertNode(&rootNode, nextNode);
    }

    vector<vector<int>> answer;

    vector<int> order;
    preOrder(&rootNode, &order);
    answer.push_back(order);

    order.clear();
    postOrder(&rootNode, &order);
    answer.push_back(order);

    // 동적 할당한 자식 노드들 메모리 해제
    deleteTree(rootNode.left);
    deleteTree(rootNode.right);

    return answer;
}