{"id":27821,"date":"2024-10-27T15:19:35","date_gmt":"2024-10-27T15:19:35","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27821"},"modified":"2024-11-26T07:14:43","modified_gmt":"2024-11-26T07:14:43","slug":"%ec%9e%90%eb%b0%94%ec%8a%a4%ed%81%ac%eb%a6%bd%ed%8a%b8-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%eb%84%88%eb%b9%84-%ec%9a%b0%ec%84%a0-%ed%83%90%ec%83%89","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27821\/","title":{"rendered":"\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9"},"content":{"rendered":"

<\/p>\n

1. \ubb38\uc81c \uc81c\uae30<\/h2>\n

\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(Breadth-First Search, BFS)\uc740 \uadf8\ub798\ud504\ub098 \ud2b8\ub9ac \uad6c\uc870\uc5d0\uc11c \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub418\ub294 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998 \uc911 \ud558\ub098\uc785\ub2c8\ub2e4. \ubcf8 \uac15\uc88c\uc5d0\uc11c\ub294 BFS\ub97c \ud65c\uc6a9\ud558\uc5ec “\ucd5c\ub2e8 \uacbd\ub85c \ucc3e\uae30” \ubb38\uc81c\ub97c \ud574\uacb0\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c: \ucd5c\ub2e8 \uacbd\ub85c \ucc3e\uae30<\/h3>\n

\uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c \ub450 \ub178\ub4dc \uc0ac\uc774\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uc2dc\uc624. \uadf8\ub798\ud504\ub294 \uc778\uc811 \ub9ac\uc2a4\ud2b8 \ud615\ud0dc\ub85c \uc8fc\uc5b4\uc9c0\uba70, \ub178\ub4dc\ub294 \ubb38\uc790\uc5f4\ub85c \ud45c\ud604\ub429\ub2c8\ub2e4.<\/p>\n

\uc785\ub825 \ud615\uc2dd<\/h4>\n
\n        graph: {\n            \"A\": [\"B\", \"C\"],\n            \"B\": [\"A\", \"D\", \"E\"],\n            \"C\": [\"A\", \"F\"],\n            \"D\": [\"B\"],\n            \"E\": [\"B\", \"F\"],\n            \"F\": [\"C\", \"E\"]\n        }\n        start: \"A\"\n        end: \"F\"\n    <\/pre>\n
\ucd9c\ub825 \ud615\uc2dd<\/h4>\n
\n        [\"A\", \"C\", \"F\"]\n    <\/pre>\n
2. \ubb38\uc81c \ubd84\uc11d<\/h2>\n
\ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\uae30 \uc704\ud574 BFS\ub97c \uc0ac\uc6a9\ud558\ub294 \uc774\uc720\ub294 BFS\uac00 \ud55c \ubc88\uc5d0 \ubaa8\ub4e0 \uc774\uc6c3 \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud558\uae30 \ub54c\ubb38\uc5d0, \uac00\uc7a5 \ube60\ub978 \uacbd\ub85c\ub97c \ubcf4\uc7a5\ud558\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9)\uc640 \ub2ec\ub9ac BFS\ub294 \ud604\uc7ac \ub178\ub4dc\uc5d0 \uc5f0\uacb0\ub41c \ubaa8\ub4e0 \ub178\ub4dc\ub97c \uba3c\uc800 \ud0d0\uc0c9\ud55c \ud6c4, \ub2e4\uc74c \ub808\ubca8\ub85c \uc774\ub3d9\ud569\ub2c8\ub2e4. \uc774 \ud2b9\uc9d5\uc73c\ub85c \uc778\ud574 BFS\ub294 \ucd5c\ub2e8 \uacbd\ub85c \ud0d0\uc0c9\uc5d0 \uc801\ud569\ud569\ub2c8\ub2e4.<\/p>\n
3. \uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h2>\n
\ub2e4\uc74c\uc740 BFS\ub97c \uc774\uc6a9\ud55c \ucd5c\ub2e8 \uacbd\ub85c \ucc3e\uae30 \uc54c\uace0\ub9ac\uc998\uc758 \uae30\ubcf8 \ud750\ub984\uc785\ub2c8\ub2e4:<\/p>\n
    \n
  1. \uc2dc\uc791 \ub178\ub4dc\ub97c \ud050\uc5d0 \ucd94\uac00\ud558\uace0 \ubc29\ubb38 \ud45c\uc2dc\ub97c \ud569\ub2c8\ub2e4.<\/li>\n
  2. \ud050\uc5d0\uc11c \ub178\ub4dc\ub97c \ud558\ub098 \uaebc\ub0b4\uace0, \uadf8 \ub178\ub4dc\uc758 \uc774\uc6c3 \ub178\ub4dc\ub97c \ubaa8\ub450 \ud655\uc778\ud569\ub2c8\ub2e4.<\/li>\n
  3. \uc774\uc6c3 \ub178\ub4dc \uc911 \ubc29\ubb38\ud558\uc9c0 \uc54a\uc740 \ub178\ub4dc\ub97c \ud050\uc5d0 \ucd94\uac00\ud558\uace0, \ud574\ub2f9 \ub178\ub4dc\uc758 \ubd80\ubaa8 \ub178\ub4dc\ub97c \ud604\uc7ac \ub178\ub4dc\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/li>\n
  4. \uc885\ub8cc \ub178\ub4dc\ub97c \ucc3e\uae30 \uc804\uae4c\uc9c0 2-3 \ub2e8\uacc4\ub97c \ubc18\ubcf5\ud569\ub2c8\ub2e4.<\/li>\n
  5. \uc885\ub8cc \ub178\ub4dc\uc5d0 \ub3c4\ub2ec\ud588\uc744 \ub54c, \ubd80\ubaa8 \ub178\ub4dc\ub97c \uac70\uafb8\ub85c \ud0d0\uc0c9\ud558\uc5ec \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uc791\uc131\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    4. \ucf54\ub4dc \uad6c\ud604<\/h2>\n
    \uc544\ub798\ub294 BFS\ub97c \uc774\uc6a9\ud55c \ucd5c\ub2e8 \uacbd\ub85c \ucc3e\uae30 \ud568\uc218\uc758 \uad6c\ud604 \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\n
    \n        function findShortestPath(graph, start, end) {\n            \/\/ \ud050\uc640 \ubc29\ubb38 \ud45c\uc2dc\ub97c \uc704\ud55c \uac1d\uccb4\n            let queue = [start];\n            let visited = {};\n            let parent = {};\n            \n            visited[start] = true;\n            parent[start] = null;\n\n            while (queue.length > 0) {\n                let currentNode = queue.shift(); \/\/ \ud050\uc5d0\uc11c \ub178\ub4dc \uc81c\uac70\n                \n                \/\/ \uc885\ub8cc \ub178\ub4dc\uc5d0 \ub3c4\ub2ec\ud55c \uacbd\uc6b0\n                if (currentNode === end) {\n                    return reconstructPath(parent, start, end);\n                }\n\n                \/\/ \ud604\uc7ac \ub178\ub4dc\uc758 \uc774\uc6c3\ub4e4 \ud0d0\uc0c9\n                for (let neighbor of graph[currentNode]) {\n                    if (!visited[neighbor]) {\n                        visited[neighbor] = true;\n                        parent[neighbor] = currentNode; \/\/ \uc774\uc6c3 \ub178\ub4dc\uc758 \ubd80\ubaa8\ub97c \ud604\uc7ac \ub178\ub4dc\ub85c \uc124\uc815\n                        queue.push(neighbor); \/\/ \ud050\uc5d0 \uc774\uc6c3 \ub178\ub4dc \ucd94\uac00\n                    }\n                }\n            }\n            return []; \/\/ \uacbd\ub85c\uac00 \uc5c6\uc744 \uacbd\uc6b0 \ube48 \ubc30\uc5f4 \ub9ac\ud134\n        }\n\n        function reconstructPath(parent, start, end) {\n            let path = [];\n            let current = end;\n            while (current !== null) {\n                path.push(current);\n                current = parent[current];\n            }\n            return path.reverse(); \/\/ \uc5ed\uc21c\uc73c\ub85c \uacbd\ub85c \ub9ac\ud134\n        }\n    <\/pre>\n
    5. \uc54c\uace0\ub9ac\uc998 \ubd84\uc11d<\/h2>\n
    \uc704 \ucf54\ub4dc\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\uae30 \uc704\ud574 BFS\ub97c \uc0ac\uc6a9\ud558\uace0 \uc788\uc2b5\ub2c8\ub2e4. \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(V + E)\ub85c, V\ub294 \ub178\ub4dc\uc758 \uc218, E\ub294 \uac04\uc120\uc758 \uc218\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \ud65c\uc6a9\ud558\uae30 \ub54c\ubb38\uc5d0 \uba54\ubaa8\ub9ac \ud6a8\uc728\uc801\uc778 \uc7a5\uc810\uc774 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
    6. \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uc640 \uacf5\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
    \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(V + E)\ub85c, \ubaa8\ub4e0 \ub178\ub4dc\uc640 \uac04\uc120\uc744 \ud55c \ubc88\uc529 \ud0d0\uc0c9\ud558\uae30 \ub54c\ubb38\uc5d0 \uc774\uc640 \uac19\uc740 \ubcf5\uc7a1\ub3c4\uac00 \ubc1c\uc0dd\ud569\ub2c8\ub2e4. \uacf5\uac04 \ubcf5\uc7a1\ub3c4 \ub610\ud55c O(V)\ub85c \ud050\uc640 \ubc29\ubb38 \ud45c\uc2dc \ubc30\uc5f4, \ubd80\ubaa8 \uc800\uc7a5 \ubc30\uc5f4 \ub4f1\uc774 \ub178\ub4dc \uc218\uc5d0 \ube44\ub840\ud558\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4.<\/p>\n
    7. \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4<\/h2>\n
    \uc704 \ucf54\ub4dc\ub97c \ud655\uc778\ud558\uae30 \uc704\ud574 \uba87 \uac00\uc9c0 \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub97c \ub9cc\ub4e4\uc5b4 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
    \n        const graph = {\n            \"A\": [\"B\", \"C\"],\n            \"B\": [\"A\", \"D\", \"E\"],\n            \"C\": [\"A\", \"F\"],\n            \"D\": [\"B\"],\n            \"E\": [\"B\", \"F\"],\n            \"F\": [\"C\", \"E\"]\n        };\n\n        console.log(findShortestPath(graph, \"A\", \"F\")); \/\/ Output: [\"A\", \"C\", \"F\"]\n        console.log(findShortestPath(graph, \"B\", \"F\")); \/\/ Output: [\"B\", \"E\", \"F\"]\n        console.log(findShortestPath(graph, \"D\", \"A\")); \/\/ Output: [\"D\", \"B\", \"A\"]\n        console.log(findShortestPath(graph, \"A\", \"A\")); \/\/ Output: [\"A\"]\n    <\/pre>\n
    8. \ub9c8\ubb34\ub9ac<\/h2>\n
    \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub85c \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(BFS)\uc744 \uc774\uc6a9\ud558\uc5ec \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud574 \ubcf4\uc558\uc2b5\ub2c8\ub2e4. BFS\ub294 \uc778\uc811 \ub9ac\uc2a4\ud2b8\uc640 \uac19\uc740 \uad6c\uc870\ub97c \ud65c\uc6a9\ud574 \uadf8\ub798\ud504\ub97c \ud0d0\uc0c9\ud558\ub294 \uc720\uc6a9\ud55c \ubc29\ubc95\uc774\uba70, \ub2e4\uc591\ud55c \ubb38\uc81c\uc5d0 \uc751\uc6a9\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc55e\uc73c\ub85c\ub3c4 \uc54c\uace0\ub9ac\uc998\uc744 \uc5f0\uc2b5\ud558\uba70 \ub354 \ub9ce\uc740 \ubb38\uc81c\ub97c \ud574\uacb0\ud574 \ub098\uac00\uae38 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n
    9. \ucd94\uac00 \uc790\ub8cc<\/h2>\n
    \ub354 \ub9ce\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc640 \ud574\ubc95\uc744 \ud559\uc2b5\ud558\uace0 \uc2f6\ub2e4\uba74 \uc628\ub77c\uc778 \ucf54\ub529 \ud14c\uc2a4\ud2b8 \ud50c\ub7ab\ud3fc\uc744 \uc774\uc6a9\ud574 \ubcf4\uc138\uc694. \uac01\uc885 \ubb38\uc81c\uc640 \ud78c\ud2b8 \ub4f1\uc744 \ud1b5\ud574 \uc2e4\ub825\uc744 \ub354\uc6b1 \ud5a5\uc0c1\uc2dc\ud0ac \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n