\uadf8\ub798\ud504\ub294 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \uac15\ub825\ud55c \ub370\uc774\ud130 \uad6c\uc870\uc785\ub2c8\ub2e4. \uc774 \ud3ec\uc2a4\ud305\uc5d0\uc11c\ub294 \uadf8\ub798\ud504\uc758 \ud45c\ud604 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uace0, \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc790\uc138\ud788 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n<\/header>\n \uadf8\ub798\ud504\ub294 \uc815\uc810(Vertex)\uacfc \uac04\uc120(Edge)\uc73c\ub85c \uad6c\uc131\ub41c \ub370\uc774\ud130 \uad6c\uc870\ub85c, \uc815\uc810\uc740 \uac1d\uccb4\ub098 \ub178\ub4dc\ub97c \ub098\ud0c0\ub0b4\uace0 \uac04\uc120\uc740 \uc815\uc810 \uac04\uc758 \uad00\uacc4\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \ubc29\ud5a5\uc774 \uc788\ub294 \uacbd\uc6b0(Directed Graph)\uc640 \uc5c6\ub294 \uacbd\uc6b0(Undirected Graph)\ub85c \ub098\ub20c \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \ub610\ud55c, \uadf8\ub798\ud504\ub294 \uac00\uc911\uce58\uac00 \uc788\uc744 \uc218\ub3c4 \uc788\uace0(Weighted Graph), \uc5c6\uc744 \uc218\ub3c4 \uc788\uc2b5\ub2c8\ub2e4(Unweighted Graph). \uac00\uc911\uce58 \uadf8\ub798\ud504\uc5d0\uc11c\ub294 \uac04\uc120\uc5d0 \ube44\uc6a9\uc774\ub098 \uac70\ub9ac\uac00 \ud560\ub2f9\ub429\ub2c8\ub2e4.<\/p>\n<\/section>\n \uadf8\ub798\ud504\ub97c \ud45c\ud604\ud558\ub294 \ubc29\ubc95\uc740 \ud06c\uac8c \ub450 \uac00\uc9c0\uac00 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n \ub2e4\uc74c \ubb38\uc81c\ub97c \ud574\uacb0\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \ubb38\uc81c \uc124\uba85:<\/strong> \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c \ub450 \uac1c\uc758 \uc815\uc810 A\uc640 B\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, A\uc5d0\uc11c B\uae4c\uc9c0 \uac00\ub294 \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ucc3e\uc544 \ucd9c\ub825\ud558\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uc138\uc694.<\/p>\n \uadf8\ub798\ud504\ub294 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub85c \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/p>\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 Depth-First Search(DFS) \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. DFS\ub294 \uadf8\ub798\ud504\uc758 \uae4a\uc774\ub97c \uc6b0\uc120\uc801\uc73c\ub85c \ud0d0\uc0c9\ud558\uc5ec \ubaa8\ub4e0 \uac00\ub2a5\ud55c \uacbd\ub85c\ub97c \ucc3e\uc544\ub0b4\ub294 \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4.<\/p>\n \uba3c\uc800, \ud604\uc7ac \uc815\uc810\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\ub294 DFS \ud568\uc218\ub97c \uc815\uc758\ud569\ub2c8\ub2e4. \uc774 \ud568\uc218\ub294 \ud604\uc7ac \uacbd\ub85c\ub97c \ub9ac\uc2a4\ud2b8\ub85c \uac00\uc9c0\uace0 \uc788\uc73c\uba70, \ubaa9\ud45c \uc815\uc810\uc5d0 \ub3c4\ub2ec\ud558\uba74 \uacbd\ub85c\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \uadf8\ub798\ud504\uc640 \uc2dc\uc791 \ubc0f \uc885\ub8cc \uc815\uc810\uc744 \uc815\uc758\ud569\ub2c8\ub2e4.<\/p>\n \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ucc3e\uae30 \uc704\ud574 \ud568\uc218\ub97c \uc2e4\ud589\ud558\uace0 \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n \uc774\ubc88 \ud3ec\uc2a4\ud305\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub97c \ud65c\uc6a9\ud55c \uadf8\ub798\ud504 \ud45c\ud604 \ubc29\uc2dd\uacfc DFS\ub97c \uc774\uc6a9\ud55c \uacbd\ub85c \ucc3e\uae30 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc124\uba85\ud588\uc2b5\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \uc2e4\uc0dd\ud65c\uc5d0\uc11c\ub3c4 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub418\ubbc0\ub85c, \uadf8 \ubcf8\uc9c8\uacfc \ud65c\uc6a9\uc5d0 \ub300\ud55c \uc774\ud574\ub294 \ub9e4\uc6b0 \uc911\uc694\ud569\ub2c8\ub2e4. \uc55e\uc73c\ub85c \ub354 \ub9ce\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uc5b4 \ubcf4\uba70, \ub2e4\uc591\ud55c \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \uae30\ub974\uc2dc\uae38 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n<\/section>\n<\/article>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\uadf8\ub798\ud504\uc758 \uc815\uc758<\/h2>\n
\uadf8\ub798\ud504 \ud45c\ud604 \ubc29\ubc95<\/h2>\n
\n
\ubb38\uc81c: \uadf8\ub798\ud504\uc758 \uacbd\ub85c \ucc3e\uae30<\/h2>\n
\ubb38\uc81c \uc608\uc2dc<\/h3>\n
\n\uc785\ub825:\ngraph = {\n 'A': ['B', 'C'],\n 'B': ['D'],\n 'C': ['D'],\n 'D': ['E'],\n 'E': []\n}\nstart = 'A'\nend = 'E'\n\n\ucd9c\ub825:\n['A', 'B', 'D', 'E']\n['A', 'C', 'D', 'E']\n <\/pre>\n<\/section>\n\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1\ub2e8\uacc4: DFS \ud568\uc218 \uc815\uc758<\/h3>\n
\nfunction findPaths(graph, start, end, path = [], paths = []) {\n path.push(start); \/\/ \ud604\uc7ac \uc815\uc810\uc744 \uacbd\ub85c\uc5d0 \ucd94\uac00\n\n \/\/ \ubaa9\ud45c \uc815\uc810\uc5d0 \ub3c4\ub2ec\ud558\uba74 \uacbd\ub85c\ub97c \uc800\uc7a5\n if (start === end) {\n paths.push([...path]);\n } else {\n \/\/ \uc778\uc811\ud55c \uc815\uc810\ub4e4\uc5d0 \ub300\ud574 DFS\ub97c \ud638\ucd9c\n for (const neighbor of graph[start] || []) {\n findPaths(graph, neighbor, end, path, paths);\n }\n }\n\n path.pop(); \/\/ \uacbd\ub85c\uc5d0\uc11c \ud604\uc7ac \uc815\uc810\uc744 \uc81c\uac70 (\ubc31\ud2b8\ub798\ud0b9)\n return paths; \/\/ \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ubc18\ud658\n}\n <\/code><\/pre>\n2\ub2e8\uacc4: \uadf8\ub798\ud504\uc640 \uc785\ub825\uac12 \uc815\uc758<\/h3>\n
\nconst graph = {\n 'A': ['B', 'C'],\n 'B': ['D'],\n 'C': ['D'],\n 'D': ['E'],\n 'E': []\n};\n\nconst start = 'A';\nconst end = 'E';\n <\/code><\/pre>\n3\ub2e8\uacc4: \ud568\uc218 \uc2e4\ud589<\/h3>\n
\nconst allPaths = findPaths(graph, start, end);\nconsole.log(allPaths);\n <\/code><\/pre>\n<\/section>\n\ucd5c\uc885 \ucf54\ub4dc<\/h2>\n
\nfunction findPaths(graph, start, end, path = [], paths = []) {\n path.push(start); \/\/ \ud604\uc7ac \uc815\uc810\uc744 \uacbd\ub85c\uc5d0 \ucd94\uac00\n if (start === end) {\n paths.push([...path]); \/\/ \uacbd\ub85c\uac00 \uc644\uc131\ub418\uba74 \ucd94\uac00\n } else {\n for (const neighbor of graph[start] || []) {\n findPaths(graph, neighbor, end, path, paths); \/\/ DFS \ud638\ucd9c\n }\n }\n path.pop(); \/\/ \ubc31\ud2b8\ub798\ud0b9\n return paths; \/\/ \ubaa8\ub4e0 \uacbd\ub85c \ubc18\ud658\n}\n\nconst graph = {\n 'A': ['B', 'C'],\n 'B': ['D'],\n 'C': ['D'],\n 'D': ['E'],\n 'E': []\n};\n\nconst start = 'A';\nconst end = 'E';\nconst allPaths = findPaths(graph, start, end);\nconsole.log(allPaths);\n <\/code><\/pre>\n<\/section>\n\uacb0\ub860<\/h2>\n