{"id":27786,"date":"2024-10-27T14:43:51","date_gmt":"2024-10-27T14:43:51","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27786"},"modified":"2024-11-26T07:15:02","modified_gmt":"2024-11-26T07:15:02","slug":"c-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ed%8a%b8%eb%a6%ac%ec%9d%98-%eb%b6%80%eb%aa%a8-%ec%b0%be%ea%b8%b0-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27786\/","title":{"rendered":"C++ \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ud2b8\ub9ac\uc758 \ubd80\ubaa8 \ucc3e\uae30"},"content":{"rendered":"

<\/p>\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\uc8fc\uc5b4\uc9c4 \uc774\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \uac01 \ub178\ub4dc\uc758 \ubd80\ubaa8 \ub178\ub4dc\ub97c \ucc3e\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694. \uc774\uc9c4 \ud2b8\ub9ac\uc758 \ub178\ub4dc\ub294 \uc22b\uc790\ub85c \ub808\uc774\ube14\uc774 \ubd99\uc5b4 \uc788\uc73c\uba70, \ub2e4\uc74c\uacfc \uac19\uc740 \uad6c\uc870\ub85c \uc815\uc758\ub429\ub2c8\ub2e4:<\/p>\n

\n    struct Node {\n        int value;\n        Node* left;\n        Node* right;\n        \n        Node(int val) : value(val), left(nullptr), right(nullptr) {}\n    };\n    <\/code><\/pre>\n
\uc785\ub825\uc73c\ub85c\ub294 \ub178\ub4dc\uc758 \ub9ac\uc2a4\ud2b8\uc640 \uc694\uccad\ub41c \ub178\ub4dc\uc758 \uac12\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. \ucd9c\ub825\uc73c\ub85c\ub294 \ud574\ub2f9 \ub178\ub4dc\uc758 \ubd80\ubaa8 \ub178\ub4dc\uc758 \uac12\uc774 \ucd9c\ub825\ub418\uc5b4\uc57c \ud558\uba70, \ubd80\ubaa8 \ub178\ub4dc\uac00 \uc5c6\ub294 \uacbd\uc6b0\uc5d0\ub294 -1\uc744 \ubc18\ud658\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\uc608\uc2dc<\/h2>\n
\n    \uc785\ub825:\n    5\n    2 1\n    7 3\n    6 4\n    0 -1\n    \uc694\uccad \ub178\ub4dc: 3\n    \n    \ucd9c\ub825:\n    7\n    <\/code><\/pre>\n
\ubb38\uc81c \uc811\uadfc \ubc29\uc2dd<\/h2>\n
\ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc774\uc9c4 \ud2b8\ub9ac\ub97c \ud0d0\uc0c9\ud558\uc5ec \uac01 \ub178\ub4dc\uc758 \ubd80\ubaa8\ub97c \ud30c\uc545\ud558\ub294 \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. \uc6b0\ub9ac\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uacfc\uc815\uc744 \ub530\ub985\ub2c8\ub2e4:<\/p>\n
    \n
  1. \ud2b8\ub9ac\uc758 \ub8e8\ud2b8 \ub178\ub4dc\ub97c \uc2dc\uc791\uc810\uc73c\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/li>\n
  2. \ud050\ub97c \uc0ac\uc6a9\ud558\uc5ec BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9) \ubc29\uc2dd\uc73c\ub85c \ud2b8\ub9ac\uc758 \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud569\ub2c8\ub2e4.<\/li>\n
  3. \uac01 \ub178\ub4dc\ub97c \ud655\uc778\ud558\uace0 \uc694\uccad\ub41c \ub178\ub4dc\uc758 \ubd80\ubaa8\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4.<\/li>\n
  4. \uc694\uccad\ub41c \ub178\ub4dc\ub97c \ucc3e\uc73c\uba74 \ud574\ub2f9 \ubd80\ubaa8 \ub178\ub4dc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    \ucf54\ub4dc \uad6c\ud604<\/h2>\n
    \n    #include \n    #include \n    #include \n    using namespace std;\n\n    struct Node {\n        int value;\n        Node* left;\n        Node* right;\n\n        Node(int val) : value(val), left(nullptr), right(nullptr) {}\n    };\n\n    Node* buildTree(const vector>& nodes) {\n        unordered_map nodeMap;\n        for (const auto& p : nodes) {\n            int child = p.first;\n            int parent = p.second;\n\n            if (nodeMap.find(child) == nodeMap.end())\n                nodeMap[child] = new Node(child);\n\n            if (parent != -1) {\n                if (nodeMap.find(parent) == nodeMap.end())\n                    nodeMap[parent] = new Node(parent);\n\n                if (!nodeMap[parent]->left)\n                    nodeMap[parent]->left = nodeMap[child];\n                else\n                    nodeMap[parent]->right = nodeMap[child];\n            }\n        }\n        return nodeMap.begin()->second; \/\/ \uccab\ubc88\uc9f8\ub85c \ucd94\uac00\ub41c \ub178\ub4dc\ub97c \ub8e8\ud2b8\ub85c \ubc18\ud658\n    }\n\n    int findParent(Node* root, int target) {\n        if (!root) return -1;\n\n        queue q;\n        q.push(root);\n        Node* parent = nullptr;\n\n        while (!q.empty()) {\n            int size = q.size();\n            for (int i = 0; i < size; ++i) {\n                Node* current = q.front();\n                q.pop();\n                \n                if (current->left) {\n                    if (current->left->value == target) {\n                        return current->value;\n                    }\n                    q.push(current->left);\n                }\n\n                if (current->right) {\n                    if (current->right->value == target) {\n                        return current->value;\n                    }\n                    q.push(current->right);\n                }\n            }\n        }\n        \n        return -1; \/\/ \ubd80\ubaa8\ub97c \ucc3e\uc9c0 \ubabb\ud55c \uacbd\uc6b0\n    }\n\n    int main() {\n        \/\/ \ud2b8\ub9ac \uad6c\uc131: (child, parent)\n        vector> nodes = {{2, 1}, {7, 3}, {6, 4}, {5, -1}};\n\n        Node* root = buildTree(nodes); \/\/ \ud2b8\ub9ac \ube4c\ub4dc\n        int target = 3; \/\/ \uc694\uccad \ub178\ub4dc\n        int parentValue = findParent(root, target);\n\n        cout << parentValue << endl; \/\/ \ubd80\ubaa8 \ucd9c\ub825\n\n        return 0;\n    }\n    <\/pair<\/node*><\/int,><\/pair<\/queue><\/unordered_map><\/iostream><\/code><\/pre>\n
    \ucf54\ub4dc \uc124\uba85<\/h2>\n
    \uc704 \ucf54\ub4dc\ub294 \uc774\uc9c4 \ud2b8\ub9ac\ub97c \ub9cc\ub4e4\uace0 \uc694\uccad\ub41c \ub178\ub4dc\uc758 \ubd80\ubaa8\ub97c \ucc3e\ub294 \uc804\ubc18\uc801\uc778 \uacfc\uc815\uc744 \ubcf4\uc5ec\uc90d\ub2c8\ub2e4.<\/p>\n