\n \ud604\ub300\uc758 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ud480\uc774\uc5d0\uc11c \uadf8\ub798\ud504\ub294 \ub9e4\uc6b0 \uc911\uc694\ud558\uace0 \uae30\ubcf8\uc801\uc778 \ub370\uc774\ud130 \uad6c\uc870\uc785\ub2c8\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 \uadf8\ub798\ud504\uc758 \ud45c\ud604 \ubc29\uc2dd\uc5d0 \ub300\ud574 \uc124\uba85\ud558\uace0, C++\uc744 \uc0ac\uc6a9\ud558\uc5ec \uad00\ub828 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \ubc30\uc6cc\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \uadf8\ub798\ud504\ub780 \uc815\uc810(vertex)\uacfc \uac04\uc120(edge)\uc73c\ub85c \uad6c\uc131\ub41c \uc790\ub8cc\uad6c\uc870\ub85c, \ub2e4\uc591\ud55c \uad00\uacc4\ub97c \ud45c\ud604\ud558\ub294 \ub370 \uc720\uc6a9\ud569\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \uc18c\uc15c \ub124\ud2b8\uc6cc\ud06c\uc5d0\uc11c\uc758 \uc0ac\uc6a9\uc790 \uac04\uc758 \uad00\uacc4, \ub3c4\ub85c\ub9dd\uc5d0\uc11c\uc758 \ub3c4\uc2dc \uac04\uc758 \uc5f0\uacb0, \uc6f9 \ud398\uc774\uc9c0 \uac04\uc758 \ub9c1\ud06c \ub4f1 \ub2e4\uc591\ud55c \uc0c1\ud669\uc5d0\uc11c \uadf8\ub798\ud504\ub97c \ud65c\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \uadf8\ub798\ud504\ub294 \uc77c\ubc18\uc801\uc73c\ub85c \ub450 \uac00\uc9c0 \ubc29\ubc95\uc73c\ub85c \ud45c\ud604\ub429\ub2c8\ub2e4: \uc778\uc811 \ud589\ub82c(Adjacency Matrix)\uacfc \uc778\uc811 \ub9ac\uc2a4\ud2b8(Adjacency List)\uc785\ub2c8\ub2e4. \uac01\uac01\uc758 \ubc29\ubc95\uc740 \uc7a5\ub2e8\uc810\uc774 \uc788\uc73c\ubbc0\ub85c, \ubb38\uc81c\uc758 \ud2b9\uc131\uc5d0 \ub530\ub77c \uc801\ud569\ud55c \ubc29\ubc95\uc744 \uc120\ud0dd\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n
\n \uc778\uc811 \ud589\ub82c\uc740 2\ucc28\uc6d0 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \ud45c\ud604\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \ud589\ub82c\uc758 \ud06c\uae30\ub294 V x V(V\ub294 \uc815\uc810\uc758 \uac1c\uc218)\ub85c, \ud589\ub82c\uc758 \uac01 \uc6d0\uc18c (i, j)\ub294 \uc815\uc810 i\uc640 \uc815\uc810 j\uac04\uc758 \uac04\uc120 \uc874\uc7ac \uc5ec\ubd80\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4.\n <\/p>\n
\n \/\/ C++\uc5d0\uc11c\uc758 \uc778\uc811 \ud589\ub82c \uc120\uc5b8\n const int MAX = 100; \/\/ \ucd5c\ub300 \uc815\uc810 \uc218\n int adj[MAX][MAX]; \/\/ \uc778\uc811 \ud589\ub82c\n int V; \/\/ \uc815\uc810\uc758 \uac1c\uc218\n <\/code><\/pre>\n\n \uc778\uc811 \ud589\ub82c\uc758 \uc7a5\uc810\uc740 \ud2b9\uc815 \uac04\uc120\uc758 \uc874\uc7ac \uc5ec\ubd80\ub97c O(1)\ub85c \ud655\uc778\ud560 \uc218 \uc788\ub2e4\ub294 \uc810\uc785\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \uba54\ubaa8\ub9ac \uce21\uba74\uc5d0\uc11c\ub294 V\uc758 \uc81c\uacf1\ub9cc\ud07c \uc0ac\uc6a9\ud558\ubbc0\ub85c, \uc815\uc810 \uc218\uac00 \ub9ce\uace0 \uac04\uc120 \uc218\uac00 \uc801\uc740 \uacbd\uc6b0 \ube44\ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.\n <\/p>\n
2. \uc778\uc811 \ub9ac\uc2a4\ud2b8<\/h3>\n
\n \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub294 \uac01 \uc815\uc810\uc5d0 \uc5f0\uacb0\ub41c \uc815\uc810\ub4e4\uc758 \ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774\ub294 \uac04\uc120\uc774 \uc801\uc740 \ud76c\uc18c \uadf8\ub798\ud504(sparse graph)\uc5d0 \ub354 \uc801\ud569\ud569\ub2c8\ub2e4.\n <\/p>\n
\n \/\/ C++\uc5d0\uc11c\uc758 \uc778\uc811 \ub9ac\uc2a4\ud2b8 \uc120\uc5b8\n #include \n #include \n using namespace std;\n\n vector adj[MAX]; \/\/ \uc778\uc811 \ub9ac\uc2a4\ud2b8\n int V; \/\/ \uc815\uc810\uc758 \uac1c\uc218\n <\/int><\/iostream><\/vector><\/code><\/pre>\n\n \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub294 \uba54\ubaa8\ub9ac\ub97c \uc880 \ub354 \ud6a8\uc728\uc801\uc73c\ub85c \uc0ac\uc6a9\ud560 \uc218 \uc788\uc73c\uba70, \uac04\uc120 \ub9ac\uc2a4\ud2b8\ub97c \uc21c\ud68c\ud558\ub294 \ub370 \uc788\uc5b4 O(E)\uc758 \uc2dc\uac04\uc774 \uc18c\uc694\ub429\ub2c8\ub2e4.\n <\/p>\n
\ubb38\uc81c: \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8 \ucc3e\uae30<\/h2>\n
\n \uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \uc8fc\uc5b4\uc9c4 \uc720\ud5a5 \uadf8\ub798\ud504\uc5d0\uc11c \uc11c\ub85c \uc5f0\uacb0\ub41c \ubaa8\ub4e0 \ucef4\ud3ec\ub10c\ud2b8\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4. \uc989, \ud558\ub098\uc758 \uc815\uc810\uc5d0\uc11c \uc2dc\uc791\ud574\uc11c \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \uc815\uc810\ub4e4\uc758 \uc9d1\ud569\uc744 \ucc3e\uc544\ub0b4\ub294 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n
\ubb38\uc81c \uc124\uba85<\/h3>\n
\n \uc815\uc810\uc758 \uc218 V\uc640 \uac04\uc120\uc758 \uc218 E\uac00 \uc8fc\uc5b4\uc9c0\uace0, \uac01 \uac04\uc120\uc740 \ub450 \uc815\uc810\uc758 \uc30d\uc73c\ub85c \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. \uc774 \uadf8\ub798\ud504\uc5d0\uc11c \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8\ub97c \ubaa8\ub450 \ucc3e\uc544 \ucd9c\ub825\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694.\n <\/p>\n
\uc785\ub825 \ud615\uc2dd<\/h3>\n\n- \uccab \ubc88\uc9f8 \uc904: \uc815\uc810\uc758 \uc218 V (1 \u2264 V \u2264 1000)<\/li>\n
- \ub450 \ubc88\uc9f8 \uc904: \uac04\uc120\uc758 \uc218 E (0 \u2264 E \u2264 10000)<\/li>\n
- \ub2e4\uc74c E \uc904: \uac04\uc120 (u, v) \ud615\ud0dc\ub85c \uc8fc\uc5b4\uc9d0<\/li>\n<\/ul>\n
\ucd9c\ub825 \ud615\uc2dd<\/h3>\n
\n \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8\uc758 \uc218\uc640 \uac01 \ucef4\ud3ec\ub10c\ud2b8\uc758 \uc815\uc810\uc744 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n
\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \uc800\uc7a5\ud558\uace0, \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS)\uc744 \ud1b5\ud574 \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8\ub97c \ucc3e\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n
1\ub2e8\uacc4: \uc778\uc811 \ub9ac\uc2a4\ud2b8 \uad6c\uc131\ud558\uae30<\/h3>\n
\n \uc6b0\uc120 \uc785\ub825\uc744 \ubc1b\uc544 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \uad6c\uc131\ud574\uc57c \ud569\ub2c8\ub2e4. \uc815\uc810\uc758 \uac1c\uc218\uc640 \uac04\uc120\uc758 \uc218\ub97c \uc785\ub825\ubc1b\uace0, \uac01 \uac04\uc120\uc744 \ud1b5\ud574 \uad00\uacc4\ub97c \ub098\ud0c0\ub0b4\ub294 \ub9ac\uc2a4\ud2b8\ub97c \uc644\uc131\ud569\ub2c8\ub2e4.\n <\/p>\n
2\ub2e8\uacc4: DFS\ub85c \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8 \ucc3e\uae30<\/h3>\n
\n \ud0d0\uc0c9\uc774 \uc774\ub8e8\uc5b4\uc9c8 \ub54c\ub9c8\ub2e4 \ubc29\ubb38\ud55c \uc815\uc810\uc744 \ub9c8\ud0b9\ud558\uace0, \ub354 \uc774\uc0c1 \ubc29\ubb38\ud560 \uc815\uc810\uc774 \uc5c6\uc744 \ub54c\uae4c\uc9c0 \ubc18\ubcf5\ud558\uba70 \ucef4\ud3ec\ub10c\ud2b8\ub97c \ucc3e\uc2b5\ub2c8\ub2e4. DFS\uc758 \uad6c\ud604\uc740 \uc7ac\uadc0\ub97c \ud1b5\ud574 \uac04\ub2e8\ud788 \uc9c4\ud589\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n #include \n #include \n #include \n\n using namespace std;\n\n vector adj[1001]; \/\/ \uc778\uc811 \ub9ac\uc2a4\ud2b8\n bool visited[1001]; \/\/ \ubc29\ubb38 \uc5ec\ubd80 \uccb4\ud06c\n vector> components; \/\/ \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8 \uc800\uc7a5\n\n void dfs(int v, vector &component) {\n visited[v] = true; \/\/ \ubc29\ubb38 \uccb4\ud06c\n component.push_back(v); \/\/ \ucef4\ud3ec\ub10c\ud2b8\uc5d0 \ucd94\uac00\n\n for (int u : adj[v]) {\n if (!visited[u]) {\n dfs(u, component); \/\/ \uc7ac\uadc0 \ud638\ucd9c\n }\n }\n }\n\n int main() {\n int V, E;\n cin >> V >> E;\n\n for (int i = 0; i < E; i++) {\n int u, v;\n cin >> u >> v; \/\/ \uac04\uc120 \uc785\ub825\n adj[u].push_back(v); \/\/ \uc778\uc811 \ub9ac\uc2a4\ud2b8 \uad6c\uc131\n adj[v].push_back(u); \/\/ \ubb34\ud5a5 \uadf8\ub798\ud504\uc784\uc744 \uac00\uc815\n }\n\n \/\/ \uac01 \uc815\uc810\uc5d0 \ub300\ud574 \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8 \ucc3e\uae30\n for (int i = 1; i <= V; i++) {\n if (!visited[i]) {\n vector component;\n dfs(i, component); \/\/ DFS \ud0d0\uc0c9\n components.push_back(component); \/\/ \ucc3e\uc740 \ucef4\ud3ec\ub10c\ud2b8 \uc800\uc7a5\n }\n }\n\n \/\/ \uacb0\uacfc \ucd9c\ub825\n cout << components.size() << \"\\n\"; \/\/ \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8 \uc218\n for (const auto &component : components) {\n sort(component.begin(), component.end()); \/\/ \ucef4\ud3ec\ub10c\ud2b8 \uc815\ub82c\n for (int v : component) {\n cout << v << \" \"; \/\/ \uc815\uc810 \ucd9c\ub825\n }\n cout << \"\\n\";\n }\n\n return 0;\n }\n <\/int><\/int><\/vector<\/int><\/algorithm><\/vector><\/iostream><\/code><\/pre>\n\n \uc704 \ucf54\ub4dc\ub97c \ud1b5\ud574 \uc785\ub825\ub41c \uadf8\ub798\ud504\uc5d0\uc11c \uc5f0\uacb0\ub41c \ucef4\ud3ec\ub10c\ud2b8\ub97c \ucc3e\uace0 \ucd9c\ub825\ud558\ub294 \ub85c\uc9c1\uc744 \uad6c\ud604\ud588\uc2b5\ub2c8\ub2e4. \uc785\ub825\ub41c \uadf8\ub798\ud504\uc758 \uac01 \ucef4\ud3ec\ub10c\ud2b8\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\uace0 \ucd9c\ub825\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4.\n <\/p>\n
\uacb0\ub860<\/h2>\n
\n \uadf8\ub798\ud504\uc758 \ud45c\ud604 \ubc29\uc2dd\uacfc DFS\ub97c \ud1b5\ud574 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \uc911\uc694\ud55c \uc5ed\ud560\uc744 \ud558\uba70, \uc774\ub97c \uc775\ud788\ub294 \uac83\uc740 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc88b\uc740 \uacb0\uacfc\ub97c \uc5bb\uae30 \uc704\ud55c \uae30\ucd08\uac00 \ub429\ub2c8\ub2e4. \uc774 \uac15\uc88c\ub97c \ud1b5\ud574 \uadf8\ub798\ud504\uc758 \uae30\ucd08\uc801\uc778 \uc774\ud574\uc640 \ubb38\uc81c \ud480\uc774 \ub2a5\ub825\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\uae38 \ubc14\ub78d\ub2c8\ub2e4.\n <\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"