{"id":445,"date":"2018-03-13T23:15:09","date_gmt":"2018-03-13T14:15:09","guid":{"rendered":"http:\/\/dong1lkim.oboki.net\/?p=445"},"modified":"2019-09-01T22:21:42","modified_gmt":"2019-09-01T13:21:42","slug":"algorithm-bfs","status":"publish","type":"post","link":"https:\/\/oboki.net\/workspace\/python\/algorithm-bfs\/","title":{"rendered":"[Algorithm] BFS"},"content":{"rendered":"<h1>Python\uc73c\ub85c \uad6c\ud604\ud55c BFS<\/h1>\n<blockquote><p>\n  BFS \uc54c\uace0\ub9ac\uc998\uc740 Queue \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud55c\ub2e4.\n<\/p><\/blockquote>\n<p>\uadf8\ub798\ud504 \ub178\ub4dc\ub97c \uc21c\ud68c\ud558\ub294\ub370 \ucd5c\ucd08 \ub178\ub4dc\uc758 \ubaa8\ub4e0 \uc790\uc2dd \ub178\ub4dc\ub4e4\uc744 \uba3c\uc800 \ud0d0\uc0c9\ud55c\ub2e4. \uc774\ud6c4 \uadf8 \uc790\uc2dd \ub178\ub4dc\ub4e4\uc758 \uc790\uc2dd \ub178\ub4dc\ub97c \ubaa8\ub450 \ud0d0\uc0c9\ud558\ub294 \uacfc\uc815\uc744 \ubc18\ubcf5\ud55c\ub2e4.<\/p>\n<h2>\uc18c\uc2a4\ucf54\ub4dc<\/h2>\n<pre><code class=\"py\">#!\/bin\/python\n\ngraph = {'A': ['B', 'C', 'D'],\n        'B': ['A', 'E', 'F'],\n        'C': ['A', 'G'],\n        'D': ['A', 'H', 'I'],\n        'E': ['B'],\n        'F': ['B', 'J'],\n        'G': ['C'],\n        'H': ['D'],\n        'I': ['D', 'K', 'L'],\n        'J': ['F'],\n        'K': ['I'],\n        'L': ['I']}\n\ndef BFS(graph, root):\n    visited = []\n    queue = [root]\n\n    while(queue):\n        outputFromQueue = queue.pop(0)\n        if outputFromQueue not in visited:\n            visited.append(outputFromQueue)\n            inputToQueue = list(set(graph[outputFromQueue]) - set(visited))\n            inputToQueue.sort()\n            queue.extend(inputToQueue)\n\n    return visited\n\nprint(BFS(graph, 'A'))\n<\/code><\/pre>\n<h2>\uc218\ud589\uacb0\uacfc<\/h2>\n<pre><code class=\"bash\">$ .\/bfs.py \n['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Python\uc73c\ub85c \uad6c\ud604\ud55c BFS BFS \uc54c\uace0\ub9ac\uc998\uc740 Queue \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud55c\ub2e4. \uadf8\ub798\ud504 \ub178\ub4dc\ub97c \uc21c\ud68c\ud558\ub294\ub370 \ucd5c\ucd08 \ub178\ub4dc\uc758 \ubaa8\ub4e0 \uc790\uc2dd \ub178\ub4dc\ub4e4\uc744 \uba3c\uc800 \ud0d0\uc0c9\ud55c\ub2e4. \uc774\ud6c4 \uadf8 \uc790\uc2dd \ub178\ub4dc\ub4e4\uc758 \uc790\uc2dd \ub178\ub4dc\ub97c \ubaa8\ub450 \ud0d0\uc0c9\ud558\ub294 \uacfc\uc815\uc744 \ubc18\ubcf5\ud55c\ub2e4. \uc18c\uc2a4\ucf54\ub4dc #!\/bin\/python graph = {&#8216;A&#8217;: [&#8216;B&#8217;, &#8216;C&#8217;, &#8216;D&#8217;], &#8216;B&#8217;: [&#8216;A&#8217;, &#8216;E&#8217;, &#8216;F&#8217;], &#8216;C&#8217;: [&#8216;A&#8217;, &#8216;G&#8217;], &#8216;D&#8217;: [&#8216;A&#8217;, &#8216;H&#8217;, &#8216;I&#8217;], &#8216;E&#8217;: [&#8216;B&#8217;], &#8216;F&#8217;: [&#8216;B&#8217;, &#8216;J&#8217;], &#8216;G&#8217;: [&#8216;C&#8217;], &#8216;H&#8217;: [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,10],"tags":[150,34],"class_list":["post-445","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-python","tag-algorithm","tag-python"],"_links":{"self":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/445","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/comments?post=445"}],"version-history":[{"count":4,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/445\/revisions"}],"predecessor-version":[{"id":1287,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/445\/revisions\/1287"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}