{"id":27736,"date":"2024-10-27T14:43:29","date_gmt":"2024-10-27T14:43:29","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27736"},"modified":"2024-11-26T07:15:43","modified_gmt":"2024-11-26T07:15:43","slug":"c-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%b5%9c%eb%8b%a8-%ea%b2%bd%eb%a1%9c-%ea%b5%ac%ed%95%98%ea%b8%b0-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27736\/","title":{"rendered":"C++ \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ucd5c\ub2e8 \uacbd\ub85c \uad6c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

1. \ubb38\uc81c \uc815\uc758<\/h2>\n

\ucd5c\ub2e8 \uacbd\ub85c \uad6c\ud558\uae30 \ubb38\uc81c\ub294 \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c \ub450 \uc815\uc810 \uc0ac\uc774\uc758 \ucd5c\uc18c \uac70\ub9ac\ub97c \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \ub178\ub4dc(\uc815\uc810)\uc640 \uc774\ub4e4\uc744 \uc5f0\uacb0\ud558\ub294 \uac04\uc120(\uc5e3\uc9c0)\uc73c\ub85c \uad6c\uc131\ub418\uba70, \uac01 \uac04\uc120\uc740 \uac70\ub9ac \ub610\ub294 \uac00\uc911\uce58\ub85c \ud45c\ud604\ub429\ub2c8\ub2e4.<\/p>\n

\uc608\ub97c \ub4e4\uc5b4, \ub2e4\uc74c\uacfc \uac19\uc740 \uadf8\ub798\ud504\uac00 \uc788\ub2e4\uace0 \uac00\uc815\ud569\uc2dc\ub2e4. \uc5ec\uae30\uc11c A, B, C, D\ub294 \ub178\ub4dc\uc774\uba70, \uac04\uc120\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uac00\uc911\uce58\ub97c \uac00\uc9d1\ub2c8\ub2e4:<\/p>\n

\n    A --1-- B\n    |      \/|\n    4     2 |\n    |  \/      |\n    C --3-- D\n    <\/pre>\n
\ubb38\uc81c\ub294 \ub450 \ub178\ub4dc A\uc640 D \uac04\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uad6c\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.<\/p>\n
2. \uc54c\uace0\ub9ac\uc998 \uc120\ud0dd<\/h2>\n
\ucd5c\ub2e8 \uacbd\ub85c \uad6c\ud558\uae30 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc77c\ubc18\uc801\uc73c\ub85c \uc0ac\uc6a9\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc775\uc2a4\ud2b8\ub77c(Dijkstra) \uc54c\uace0\ub9ac\uc998\uacfc \ubca8\ub9cc-\ud3ec\ub4dc(Bellman-Ford) \uc54c\uace0\ub9ac\uc998\uc774 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uaca0\uc2b5\ub2c8\ub2e4. \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 \uac00\uc911\uce58\uac00 \uc74c\uc218\uac00 \uc544\ub2cc \uadf8\ub798\ud504\uc5d0\uc11c \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ub370 \uc801\ud569\ud569\ub2c8\ub2e4.<\/p>\n
2.1 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998 \uc124\uba85<\/h3>\n
\ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4:<\/p>\n
    \n
  1. \uc2dc\uc791 \ub178\ub4dc\ub97c \uc124\uc815\ud558\uace0, \uadf8 \ub178\ub4dc\uc5d0 \ub300\ud55c \ucd5c\ub2e8 \uac70\ub9ac\ub97c 0\uc73c\ub85c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.<\/li>\n
  2. \ubaa8\ub4e0 \ub2e4\ub978 \ub178\ub4dc\uc758 \ucd5c\ub2e8 \uac70\ub9ac\ub97c \ubb34\ud55c\ub300\ub85c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.<\/li>\n
  3. \ubc29\ubb38\ud558\uc9c0 \uc54a\uc740 \ub178\ub4dc \uc911 \uac00\uc7a5 \ucd5c\ub2e8 \uac70\ub9ac \uac12\uc774 \ub0ae\uc740 \ub178\ub4dc\ub97c \uc120\ud0dd\ud569\ub2c8\ub2e4.<\/li>\n
  4. \uc774 \ub178\ub4dc\ub97c \ud604\uc7ac \ub178\ub4dc\ub85c \uc124\uc815\ud558\uace0, \uc774 \ub178\ub4dc\ub97c \ud1b5\ud574 \uc811\uadfc\ud560 \uc218 \uc788\ub294 \ubaa8\ub4e0 \uc778\uc811 \ub178\ub4dc\uc758 \ucd5c\ub2e8 \uac70\ub9ac \uac12\uc744 \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4.<\/li>\n
  5. \ubaa8\ub4e0 \ub178\ub4dc\ub97c \ubc29\ubb38\ud560 \ub54c\uae4c\uc9c0 3-4 \ub2e8\uacc4\ub97c \ubc18\ubcf5\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    3. C++ \uad6c\ud604<\/h2>\n
    \uc774\uc81c C++\ub85c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c\uc740 \uc704\uc5d0\uc11c \uc124\uba85\ud55c \uadf8\ub798\ud504\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\n
    \n#include <iostream>\n#include <vector>\n#include <queue>\n#include <limits> \/\/ numeric_limits\ub97c \uc704\ud574\nusing namespace std;\n\n\/\/ \uadf8\ub798\ud504 \uad6c\uc870\uccb4 \uc815\uc758\nstruct Edge {\n    int destination;\n    int weight;\n};\n\n\/\/ \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998 \uad6c\ud604\nvector dijkstra(int start, const vector>& graph) {\n    int n = graph.size();\n    vector distance(n, numeric_limits::max());\n    distance[start] = 0;\n    \n    priority_queue, vector>, greater>> minHeap;\n    minHeap.push({0, start});\n\n    while (!minHeap.empty()) {\n        int currentDistance = minHeap.top().first;\n        int currentNode = minHeap.top().second;\n        minHeap.pop();\n\n        \/\/ \ud604\uc7ac \ub178\ub4dc\uc758 \uac70\ub9ac \uac12\uc774 \ub354 \ud06c\uba74 \ubb34\uc2dc\n        if (currentDistance > distance[currentNode]) continue;\n\n        \/\/ \uc778\uc811 \ub178\ub4dc \ud0d0\uc0c9\n        for (const Edge& edge : graph[currentNode]) {\n            int newDistance = currentDistance + edge.weight;\n            if (newDistance < distance[edge.destination]) {\n                distance[edge.destination] = newDistance;\n                minHeap.push({newDistance, edge.destination});\n            }\n        }\n    }\n\n    return distance;\n}\n\nint main() {\n    \/\/ \uadf8\ub798\ud504 \ucd08\uae30\ud654\n    int n = 4; \/\/ \ub178\ub4dc \uac1c\uc218\n    vector> graph(n);\n    \n    \/\/ \uac04\uc120 \ucd94\uac00 (0-based index)\n    graph[0].push_back({1, 1});\n    graph[0].push_back({2, 4});\n    graph[1].push_back({2, 2});\n    graph[1].push_back({3, 1});\n    graph[2].push_back({3, 3});\n    \n    int startNode = 0; \/\/ A\n    vector shortestPaths = dijkstra(startNode, graph);\n\n    \/\/ \uacb0\uacfc \ucd9c\ub825\n    cout << \"\ucd5c\ub2e8 \uacbd\ub85c:\" << endl;\n    for (int i = 0; i < n; i++) {\n        cout << \"A\uc5d0\uc11c \" << char('A' + i) << \"\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c: \";\n        if (shortestPaths[i] == numeric_limits::max()) {\n            cout << \"\ub3c4\ub2ec \ubd88\uac00\ub2a5\" << endl;\n        } else {\n            cout << shortestPaths[i] << endl;\n        }\n    }\n\n    return 0;\n}\n    <\/int><\/int><\/vector<\/pair<\/pair<\/pair<\/int><\/int><\/vector<\/int><\/pre>\n
    4. \ucf54\ub4dc \uc124\uba85<\/h2>\n
    4.1 \uadf8\ub798\ud504 \uad6c\uc870 \uc124\uc815<\/h3>\n
    \uba3c\uc800, \uac04\uc120 \uad6c\uc870\uccb4\ub97c \uc815\uc758\ud558\uc5ec \uac01 \ub178\ub4dc\uc640 \uac00\uc911\uce58 \uc815\ubcf4\ub97c \ud3ec\ud568\ud55c \uadf8\ub798\ud504\ub97c \uc124\uc815\ud569\ub2c8\ub2e4. vector<vector<Edge>><\/code>\ub97c \uc0ac\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \ud45c\ud604\ud569\ub2c8\ub2e4.<\/p>\n
    4.2 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uad6c\ud604<\/h3>\n
    \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uc704\ud55c \ud568\uc218 dijkstra<\/code>\ub97c \uc791\uc131\ud588\uc2b5\ub2c8\ub2e4. \uc2dc\uc791 \ub178\ub4dc\uc5d0\uc11c\ubd80\ud130 \uac01 \ub178\ub4dc\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uac70\ub9ac\ub97c \uacc4\uc0b0\ud558\uc5ec distance<\/code> \ubca1\ud130\uc5d0 \uc800\uc7a5\ud569\ub2c8\ub2e4. priority_queue<\/code>\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud604\uc7ac\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uad00\ub9ac\ud569\ub2c8\ub2e4.<\/p>\n
    4.3 \uba54\uc778 \ud568\uc218<\/h3>\n
    main<\/code> \ud568\uc218\uc5d0\uc11c \uadf8\ub798\ud504\ub97c \ucd08\uae30\ud654\ud558\uace0, \ub2e4\uc775\uc2a4\ud2b8\ub77c \ud568\uc218\ub97c \ud638\ucd9c\ud558\uc5ec \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uad6c\ud55c \ub4a4, \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n
    5. \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
    \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \uc0ac\uc6a9\ub41c \uc790\ub8cc \uad6c\uc870\uc5d0 \ub530\ub77c \ub2ec\ub77c\uc9d1\ub2c8\ub2e4. \uc77c\ubc18\uc801\uc73c\ub85c \ud799\uc744 \uc0ac\uc6a9\ud560 \uacbd\uc6b0 O(E log V)<\/code>\ub85c \ub098\ud0c0\ub0b4\uba70, \uc5ec\uae30\uc11c E<\/code>\ub294 \uac04\uc120\uc758 \uc218, V<\/code>\ub294 \ub178\ub4dc\uc758 \uc218\uc785\ub2c8\ub2e4.<\/p>\n
    6. \ucc38\uace0 \uc790\ub8cc<\/h2>\n