{"id":3964,"date":"2024-07-27T16:05:53","date_gmt":"2024-07-27T07:05:53","guid":{"rendered":"https:\/\/itjaeneungnanum.org\/?p=3964"},"modified":"2024-07-27T16:07:52","modified_gmt":"2024-07-27T07:07:52","slug":"003-%ea%b9%8a%ec%9d%b4-%ec%9a%b0%ec%84%a0-%ed%83%90%ec%83%89dfs%ea%b3%bc-%eb%84%88%eb%b9%84-%ec%9a%b0%ec%84%a0-%ed%83%90%ec%83%89bfs","status":"publish","type":"post","link":"https:\/\/itjaeneungnanum.org\/?p=3964","title":{"rendered":"003. \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS)\uacfc \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(BFS)"},"content":{"rendered":"\n<p>\uba3c\uc800, \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS)\uc5d0 \ub300\ud574 \uc0b4\ud3b4 \ubd05\ub2c8\ub2e4<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"375\" height=\"241\" src=\"https:\/\/itjaeneungnanum.org\/wp-content\/uploads\/2024\/07\/Depth-first-tree.svg_.png\" alt=\"\" class=\"wp-image-3965\" srcset=\"https:\/\/itjaeneungnanum.org\/wp-content\/uploads\/2024\/07\/Depth-first-tree.svg_.png 375w, https:\/\/itjaeneungnanum.org\/wp-content\/uploads\/2024\/07\/Depth-first-tree.svg_-300x193.png 300w\" sizes=\"(max-width: 375px) 100vw, 375px\" \/><\/figure>\n\n\n\n<p>\uc704 \uc774\ubbf8\uc9c0\ub97c \uc0ac\uc6a9\ud558\uc5ec \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS) \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uc124\uba85\ud574 \ub4dc\ub9ac\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n\n\n\n<p>\uc774 \uc774\ubbf8\uc9c0\ub294 \uc774\uc9c4 \ud2b8\ub9ac \uad6c\uc870\ub97c \ubcf4\uc5ec\uc8fc\uace0 \uc788\uc2b5\ub2c8\ub2e4. DFS \uc54c\uace0\ub9ac\uc998\uc774 \uc774 \ud2b8\ub9ac\ub97c \uc5b4\ub5bb\uac8c \ud0d0\uc0c9\ud560\uc9c0 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n\n\n\n<ol><li>\uc2dc\uc791: \ub8e8\ud2b8 \ub178\ub4dc\uc778 1\uc5d0\uc11c \uc2dc\uc791\ud569\ub2c8\ub2e4.<\/li><li>\uc67c\ucabd \uc6b0\uc120 \ud0d0\uc0c9:<ul><li>1 -> 2 -> 3 -> 4\ub85c \uc774\ub3d9\ud569\ub2c8\ub2e4.<\/li><li>4\ub294 \ub9ac\ud504 \ub178\ub4dc\uc774\ubbc0\ub85c, 3\uc73c\ub85c \ubc31\ud2b8\ub798\ud0b9\ud569\ub2c8\ub2e4.<\/li><li>3\uc758 \uc624\ub978\ucabd \uc790\uc2dd\uc778 5\ub97c \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><li>5\ub3c4 \ub9ac\ud504 \ub178\ub4dc\uc774\ubbc0\ub85c, 2\ub85c \ubc31\ud2b8\ub798\ud0b9\ud569\ub2c8\ub2e4.<\/li><li>2\uc758 \uc624\ub978\ucabd \uc790\uc2dd\uc778 6\uc744 \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><\/ul><\/li><li>\uc911\uac04 \ub178\ub4dc \ud0d0\uc0c9:<ul><li>6\uc5d0\uc11c \ub354 \uc774\uc0c1 \uc790\uc2dd\uc774 \uc5c6\uc73c\ubbc0\ub85c, 1\ub85c \ubc31\ud2b8\ub798\ud0b9\ud569\ub2c8\ub2e4.<\/li><li>1\uc758 \uc911\uac04 \uc790\uc2dd\uc778 7\uc744 \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><\/ul><\/li><li>\uc624\ub978\ucabd \uc11c\ube0c\ud2b8\ub9ac \ud0d0\uc0c9:<ul><li>7\uc5d0\uc11c \uc790\uc2dd\uc774 \uc5c6\uc73c\ubbc0\ub85c, \ub2e4\uc2dc 1\ub85c \ubc31\ud2b8\ub798\ud0b9\ud569\ub2c8\ub2e4.<\/li><li>1\uc758 \uc624\ub978\ucabd \uc790\uc2dd\uc778 8\ub85c \uc774\ub3d9\ud569\ub2c8\ub2e4.<\/li><li>8 -> 9 -> 10\uc73c\ub85c \uc774\ub3d9\ud569\ub2c8\ub2e4.<\/li><li>10\uc740 \ub9ac\ud504 \ub178\ub4dc\uc774\ubbc0\ub85c, 9\ub85c \ubc31\ud2b8\ub798\ud0b9\ud569\ub2c8\ub2e4.<\/li><li>9\uc758 \uc624\ub978\ucabd \uc790\uc2dd\uc778 11\uc744 \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><li>11\uc5d0\uc11c 8\ub85c \ubc31\ud2b8\ub798\ud0b9\ud558\uace0, 8\uc758 \uc624\ub978\ucabd \uc790\uc2dd\uc778 12\ub97c \ub9c8\uc9c0\ub9c9\uc73c\ub85c \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><\/ul><\/li><\/ol>\n\n\n\n<p>\ub530\ub77c\uc11c DFS\uc758 \ubc29\ubb38 \uc21c\uc11c\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12<\/p>\n\n\n\n<p>\uc774 \uacfc\uc815\uc5d0\uc11c DFS\ub294 \ud56d\uc0c1 \uac00\ub2a5\ud55c \ud55c \uae4a\uc774 \ub4e4\uc5b4\uac00\uba70, \ub354 \uc774\uc0c1 \uac08 \uacf3\uc774 \uc5c6\uc744 \ub54c\ub9cc \ubc31\ud2b8\ub798\ud0b9\ud558\uc5ec \ub2e4\ub978 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud569\ub2c8\ub2e4. \uc774 \ubc29\uc2dd\uc73c\ub85c \ud2b8\ub9ac\uc758 \ubaa8\ub4e0 \ub178\ub4dc\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ubc29\ubb38\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n\n\n\n<p>\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9\uc744 \uad6c\ud604\ud558\ub294 \ud30c\uc774\uc36c \ucf54\ub4dc\ub294 \uc544\ub798\uc640 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Node:\n    def __init__(self, value):\n        self.value = value\n        self.left = None\n        self.right = None\n        self.middle = None  # \uc911\uac04 \uc790\uc2dd\uc744 \uc704\ud55c \ucd94\uac00 \ud3ec\uc778\ud130\n\ndef dfs(node):\n    if node is None:\n        return\n    \n    print(node.value, end=' ')  # \ud604\uc7ac \ub178\ub4dc \ubc29\ubb38\n    \n    dfs(node.left)    # \uc67c\ucabd \uc11c\ube0c\ud2b8\ub9ac \ud0d0\uc0c9\n    dfs(node.middle)  # \uc911\uac04 \uc11c\ube0c\ud2b8\ub9ac \ud0d0\uc0c9\n    dfs(node.right)   # \uc624\ub978\ucabd \uc11c\ube0c\ud2b8\ub9ac \ud0d0\uc0c9\n\n# \ud2b8\ub9ac \uad6c\uc131\nroot = Node(1)\nroot.left = Node(2)\nroot.middle = Node(7)\nroot.right = Node(8)\n\nroot.left.left = Node(3)\nroot.left.right = Node(6)\n\nroot.left.left.left = Node(4)\nroot.left.left.right = Node(5)\n\nroot.right.left = Node(9)\nroot.right.right = Node(12)\n\nroot.right.left.left = Node(10)\nroot.right.left.right = Node(11)\n\n# DFS \uc2e4\ud589\nprint(\"DFS \uc21c\ud68c \uacb0\uacfc:\")\ndfs(root)<\/code><\/pre>\n\n\n\n<p>\ub2e4\uc74c\uc73c\ub85c \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9\uc5d0 \ub300\ud574\uc11c \uc0b4\ud3b4 \ubd05\ub2c8\ub2e4.<\/p>\n\n\n\n<p>\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9\uc740 \ud2b8\ub9ac\ub098 \uadf8\ub798\ud504 \uad6c\uc870\uc5d0\uc11c \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud558\ub294 \ubc29\ubc95 \uc911 \ud558\ub098\ub85c, \ub8e8\ud2b8 \ub178\ub4dc\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \uc778\uc811\ud55c \ub178\ub4dc\ub97c \uba3c\uc800 \ud0d0\uc0c9\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc544\ub798 \uc774\ubbf8\uc9c0\uc758 \ud2b8\ub9ac\ub97c \uae30\uc900\uc73c\ub85c BFS \uacfc\uc815\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"450\" height=\"289\" src=\"https:\/\/itjaeneungnanum.org\/wp-content\/uploads\/2024\/07\/Breadth-first-tree.svg_.png\" alt=\"\" class=\"wp-image-3968\" srcset=\"https:\/\/itjaeneungnanum.org\/wp-content\/uploads\/2024\/07\/Breadth-first-tree.svg_.png 450w, https:\/\/itjaeneungnanum.org\/wp-content\/uploads\/2024\/07\/Breadth-first-tree.svg_-300x193.png 300w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/figure>\n\n\n\n<ol><li>\uc2dc\uc791: \ub8e8\ud2b8 \ub178\ub4dc\uc778 1\uc5d0\uc11c \uc2dc\uc791\ud569\ub2c8\ub2e4.<\/li><li>\uccab \ubc88\uc9f8 \ub808\ubca8:<ul><li>1\uc758 \ubaa8\ub4e0 \uc790\uc2dd \ub178\ub4dc\uc778 2, 3, 4\ub97c \uc21c\uc11c\ub300\ub85c \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><\/ul><\/li><li>\ub450 \ubc88\uc9f8 \ub808\ubca8:<ul><li>2\uc758 \uc790\uc2dd \ub178\ub4dc\uc778 5, 6\uc744 \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><li>3\uc740 \uc790\uc2dd\uc774 \uc5c6\uc73c\ubbc0\ub85c \ub118\uc5b4\uac11\ub2c8\ub2e4.<\/li><li>4\uc758 \uc790\uc2dd \ub178\ub4dc\uc778 7, 8\uc744 \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><\/ul><\/li><li>\uc138 \ubc88\uc9f8 \ub808\ubca8:<ul><li>5\uc758 \uc790\uc2dd \ub178\ub4dc\uc778 9, 10\uc744 \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><li>6, 7\uc740 \uc790\uc2dd\uc774 \uc5c6\uc73c\ubbc0\ub85c \ub118\uc5b4\uac11\ub2c8\ub2e4.<\/li><li>8\uc758 \uc790\uc2dd \ub178\ub4dc\uc778 11, 12\ub97c \ubc29\ubb38\ud569\ub2c8\ub2e4.<\/li><\/ul><\/li><\/ol>\n\n\n\n<p>\ub530\ub77c\uc11c BFS\uc758 \ubc29\ubb38 \uc21c\uc11c\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12<\/p>\n\n\n\n<p>BFS\uc758 \uc8fc\uc694 \ud2b9\uc9d5:<\/p>\n\n\n\n<ol><li>\uac19\uc740 \ub808\ubca8\uc5d0 \uc788\ub294 \ub178\ub4dc\ub4e4\uc744 \ubaa8\ub450 \ubc29\ubb38\ud55c \ud6c4 \ub2e4\uc74c \ub808\ubca8\ub85c \ub118\uc5b4\uac11\ub2c8\ub2e4.<\/li><li>\uc8fc\ub85c \ud050(Queue) \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ud569\ub2c8\ub2e4.<\/li><li>\ucd9c\ubc1c\uc810\uc5d0\uc11c \uac00\uae4c\uc6b4 \ub178\ub4dc\ubd80\ud130 \ud0d0\uc0c9\ud558\ubbc0\ub85c, \ucd5c\ub2e8 \uacbd\ub85c \ubb38\uc81c \ud574\uacb0\uc5d0 \uc801\ud569\ud569\ub2c8\ub2e4.<\/li><li>\uba54\ubaa8\ub9ac \uc0ac\uc6a9\ub7c9\uc774 DFS\uc5d0 \ube44\ud574 \ud06c\uc9c0\ub9cc, \ubaa9\ud45c \ub178\ub4dc\uac00 \uc595\uc740 \uae4a\uc774\uc5d0 \uc788\uc744 \ub54c \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/li><\/ol>\n\n\n\n<p>BFS\ub294 \ub124\ud2b8\uc6cc\ud06c \ud0d0\uc0c9, \ucd5c\ub2e8 \uacbd\ub85c \ucc3e\uae30, \uc6f9 \ud06c\ub864\ub9c1 \ub4f1 \ub2e4\uc591\ud55c \ubd84\uc57c\uc5d0\uc11c \ud65c\uc6a9\ub429\ub2c8\ub2e4.<\/p>\n\n\n\n<p>\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9\uc758 \ud30c\uc774\uc36c \ucf54\ub4dc\ub294 \uc544\ub798\uc640 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>from collections import deque\n\nclass Node:\n    def __init__(self, value):\n        self.value = value\n        self.children = &#91;]\n\ndef bfs(root):\n    if not root:\n        return\n\n    queue = deque(&#91;root])\n    result = &#91;]\n\n    while queue:\n        node = queue.popleft()\n        result.append(node.value)\n\n        for child in node.children:\n            queue.append(child)\n\n    return result\n\n# \ud2b8\ub9ac \uad6c\uc131\nroot = Node(1)\nroot.children = &#91;Node(2), Node(3), Node(4)]\nroot.children&#91;0].children = &#91;Node(5), Node(6)]\nroot.children&#91;2].children = &#91;Node(7), Node(8)]\nroot.children&#91;0].children&#91;0].children = &#91;Node(9), Node(10)]\nroot.children&#91;2].children&#91;1].children = &#91;Node(11), Node(12)]\n\n# BFS \uc2e4\ud589\nbfs_result = bfs(root)\nprint(\"BFS \uc21c\ud68c \uacb0\uacfc:\", bfs_result)<\/code><\/pre>\n\n\n\n<p><\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<div class=\"ast-oembed-container\" style=\"height: 100%;\"><iframe loading=\"lazy\" title=\"\u110e\u1161\u11af\u1109\u1173\u110b\u1174 \u110b\u1161\u11af\u1100\u1169\u1105\u1175\u110c\u1173\u11b7 \u1106\u116e\u11ab\u110c\u1166\u1111\u116e\u11af\u110b\u1175(3) - BFS(Breadth First Search), DFS(Depth First Search)\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/OchIoOoJ8jU?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/div>\n<\/div><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\uba3c\uc800, \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS)\uc5d0 \ub300\ud574 \uc0b4\ud3b4 \ubd05\ub2c8\ub2e4 \uc704 \uc774\ubbf8\uc9c0\ub97c \uc0ac\uc6a9\ud558\uc5ec \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS) \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uc124\uba85\ud574 \ub4dc\ub9ac\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \uc774\ubbf8\uc9c0\ub294 \uc774\uc9c4 \ud2b8\ub9ac \uad6c\uc870\ub97c \ubcf4\uc5ec\uc8fc\uace0 \uc788\uc2b5\ub2c8\ub2e4. DFS \uc54c\uace0\ub9ac\uc998\uc774 \uc774 \ud2b8\ub9ac\ub97c \uc5b4\ub5bb\uac8c \ud0d0\uc0c9\ud560\uc9c0 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4: \uc2dc\uc791: \ub8e8\ud2b8 \ub178\ub4dc\uc778 1\uc5d0\uc11c \uc2dc\uc791\ud569\ub2c8\ub2e4. \uc67c\ucabd \uc6b0\uc120 \ud0d0\uc0c9: 1 -> 2 -> 3 -> 4\ub85c \uc774\ub3d9\ud569\ub2c8\ub2e4. 4\ub294 \ub9ac\ud504 \ub178\ub4dc\uc774\ubbc0\ub85c, 3\uc73c\ub85c \ubc31\ud2b8\ub798\ud0b9\ud569\ub2c8\ub2e4. 3\uc758 \uc624\ub978\ucabd \uc790\uc2dd\uc778 &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"\" href=\"https:\/\/itjaeneungnanum.org\/?p=3964\"> <span class=\"screen-reader-text\">003. \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS)\uacfc \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(BFS)<\/span> \ub354 \ubcf4\uae30 &raquo;<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"default","ast-global-header-display":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":""},"categories":[40],"tags":[],"_links":{"self":[{"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/posts\/3964"}],"collection":[{"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3964"}],"version-history":[{"count":2,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/posts\/3964\/revisions"}],"predecessor-version":[{"id":3969,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/posts\/3964\/revisions\/3969"}],"wp:attachment":[{"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3964"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3964"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3964"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}