{"id":27851,"date":"2024-10-27T15:19:54","date_gmt":"2024-10-27T15:19:54","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27851"},"modified":"2024-11-26T07:14:27","modified_gmt":"2024-11-26T07:14:27","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-dfs%ec%99%80-bfs-%ed%94%84%eb%a1%9c%ea%b7%b8%eb%9e%a8","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27851\/","title":{"rendered":"\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, DFS\uc640 BFS \ud504\ub85c\uadf8\ub7a8"},"content":{"rendered":"

<\/p>\n

\n
\n

\ube14\ub85c\uadf8\uc5d0 \uc624\uc2e0 \uac83\uc744 \ud658\uc601\ud569\ub2c8\ub2e4! \uc624\ub298\uc740 DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9)\uc640 BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9) \uc54c\uace0\ub9ac\uc998\uc744 \ud65c\uc6a9\ud55c \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uba70 \uc774\ub860\uacfc \uc2e4\uc81c \uad6c\ud604\uc744 \ub3d9\uc2dc\uc5d0 \ud559\uc2b5\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n<\/header>\n

\n

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

\uc8fc\uc5b4\uc9c4 \ubb34\ubc29\ud5a5 \uadf8\ub798\ud504\uc5d0\uc11c \ud2b9\uc815 \ub178\ub4dc\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uaca0\uc2b5\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \uc778\uc811 \ub9ac\uc2a4\ud2b8 \ud615\ud0dc\ub85c \uc8fc\uc5b4\uc9c0\uba70, \ucd5c\ub2e8 \uacbd\ub85c\ub294 BFS\ub85c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. DFS\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\uae30\ubcf4\ub2e4\ub294 \uacbd\ub85c\uc758 \uc874\uc7ac \uc5ec\ubd80\ub97c \ud655\uc778\ud558\ub294 \ub370 \uc0ac\uc6a9\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c<\/h3>\n
\n\uc785\ub825:\n- n: \uc815\uc810\uc758 \uc218 (1 \u2264 n \u2264 10^4)\n- edges: \uac04\uc120 \ub9ac\uc2a4\ud2b8 (\ubb34\ubc29\ud5a5)\n- start: \uc2dc\uc791 \uc815\uc810\n- end: \uc885\ub8cc \uc815\uc810\n\n\ucd9c\ub825:\n- start\uc5d0\uc11c end\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uc774\ub8e8\ub294 \uac04\uc120\uc758 \ub9ac\uc2a4\ud2b8\n            <\/code><\/pre>\n
\uc608\uc2dc<\/h3>\n
\uc785\ub825:<\/strong> n = 5<\/code>, edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]]<\/code>, start = 1<\/code>, end = 5<\/code><\/p>\n
\ucd9c\ub825:<\/strong> [1, 2, 4, 5]<\/code> \ub610\ub294 [1, 3, 4, 5]<\/code><\/p>\n<\/section>\n
\n
\uc774\ub860<\/h2>\n
DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9)<\/h3>\n
\n                DFS\ub294 \uadf8\ub798\ud504\uc758 \ud55c \ub178\ub4dc\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \uac00\ub2a5\ud55c \ud55c \uae4a\uc219\uc774 \ud0d0\uc0c9\ud55c \ud6c4 \ub354 \uc774\uc0c1 \uc9c4\ud589\ud560 \uc218 \uc5c6\uac8c \ub418\uba74 \ub418\ub3cc\uc544\uac00\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uc7ac\uadc0\uc801\uc73c\ub85c \ub610\ub294 \uc2a4\ud0dd\uc744 \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ub429\ub2c8\ub2e4. DFS\uc758 \uc7a5\uc810\uc740 \uba54\ubaa8\ub9ac \uc0ac\uc6a9\ub7c9\uc774 \uc801\uace0, \uae4a\uc740 \ub178\ub4dc \ud0d0\uc0c9\uc774 \ud544\uc694\ud55c \uacbd\uc6b0\uc5d0 \uc720\uc6a9\ud569\ub2c8\ub2e4.\n            <\/p>\n
BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9)<\/h3>\n
\n                BFS\ub294 \uc2dc\uc791 \ub178\ub4dc\uc5d0\uc11c \uc778\uc811\ud55c \ubaa8\ub4e0 \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud55c \ud6c4, \uadf8 \ub178\ub4dc\ub4e4\uc758 \uc778\uc811 \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uc9c4\ud589\ub429\ub2c8\ub2e4. \ud050\ub97c \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ud558\uba70, \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\uae30\uc5d0 \ud2b9\ud788 \uc801\ud569\ud569\ub2c8\ub2e4. BFS\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ub370 \uc788\uc5b4 \ub9e4\uc6b0 \uc720\uc6a9\ud558\uba70, \ucd5c\ub2e8 \uacbd\ub85c\uac00 \uc874\uc7ac\ud560 \uacbd\uc6b0 \uc774\ub97c \ubcf4\uc7a5\ud569\ub2c8\ub2e4.\n            <\/p>\n<\/section>\n
\n
\ubb38\uc81c \ud480\uc774<\/h2>\n
1\ub2e8\uacc4: \uadf8\ub798\ud504 \uad6c\uc131<\/h3>\n
\uba3c\uc800, \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \uad6c\uc131\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\nfunction buildGraph(n, edges) {\n    const graph = Array.from({ length: n + 1 }, () => []);\n    for (const [u, v] of edges) {\n        graph[u].push(v);\n        graph[v].push(u); \/\/ \ubb34\ubc29\ud5a5 \uadf8\ub798\ud504\uc774\ubbc0\ub85c \uc591\ubc29\ud5a5\uc73c\ub85c \ucd94\uac00\n    }\n    return graph;\n}\n\nconst n = 5;\nconst edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]];\nconst graph = buildGraph(n, edges);\nconsole.log(graph);\n            <\/code><\/pre>\n
2\ub2e8\uacc4: BFS \uad6c\ud604<\/h3>\n
\uc774\uc81c \uc2dc\uc791 \uc815\uc810\uc5d0\uc11c \uc885\ub8cc \uc815\uc810\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c BFS\ub85c \ucc3e\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\nfunction bfs(graph, start, end) {\n    const queue = [[start]];\n    const visited = new Set([start]);\n\n    while (queue.length > 0) {\n        const path = queue.shift();\n        const node = path[path.length - 1];\n\n        if (node === end) {\n            return path; \/\/ \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\uc73c\uba74 \ubc18\ud658\n        }\n\n        for (const neighbor of graph[node]) {\n            if (!visited.has(neighbor)) {\n                visited.add(neighbor);\n                queue.push([...path, neighbor]); \/\/ \ud604\uc7ac \uacbd\ub85c\uc5d0 \uc778\uc811 \ub178\ub4dc\ub97c \ucd94\uac00\n            }\n        }\n    }\n    return []; \/\/ \uacbd\ub85c\uac00 \uc5c6\uc744 \uacbd\uc6b0 \ube48 \ubc30\uc5f4 \ubc18\ud658\n}\n\nconst start = 1,\n      end = 5;\n\nconst result = bfs(graph, start, end);\nconsole.log(result);\n            <\/code><\/pre>\n
3\ub2e8\uacc4: DFS \uad6c\ud604<\/h3>\n
\uc774\uc81c DFS\ub97c \uc0ac\uc6a9\ud558\uc5ec \uacbd\ub85c\uc758 \uc874\uc7ac \uc5ec\ubd80\ub97c \ud655\uc778\ud558\uace0, \uacbd\ub85c\ub97c \ucc3e\ub294 \ubc29\ubc95\uc744 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\nfunction dfs(graph, start, end, visited = new Set(), path = []) {\n    visited.add(start);\n    path.push(start);\n    \n    if (start === end) {\n        return path; \/\/ \uacbd\ub85c\ub97c \ucc3e\uc73c\uba74 \ubc18\ud658\n    }\n\n    for (const neighbor of graph[start]) {\n        if (!visited.has(neighbor)) {\n            const resultPath = dfs(graph, neighbor, end, visited, [...path]);\n            if (resultPath.length > 0) {\n                return resultPath; \/\/ \uacbd\ub85c\uac00 \ubc1c\uacac\ub418\uba74 \ubc18\ud658\n            }\n        }\n    }\n    return []; \/\/ \uacbd\ub85c\uac00 \uc5c6\uc744 \uacbd\uc6b0 \ube48 \ubc30\uc5f4 \ubc18\ud658\n}\n\nconst dfsResult = dfs(graph, start, end);\nconsole.log(dfsResult);\n            <\/code><\/pre>\n<\/section>\n