{"id":443,"date":"2018-03-13T22:24:37","date_gmt":"2018-03-13T13:24:37","guid":{"rendered":"http:\/\/dong1lkim.oboki.net\/?p=443"},"modified":"2019-09-01T22:21:50","modified_gmt":"2019-09-01T13:21:50","slug":"algorithm-dfs","status":"publish","type":"post","link":"https:\/\/oboki.net\/workspace\/python\/algorithm-dfs\/","title":{"rendered":"[Algorithm] DFS"},"content":{"rendered":"

Python\uc73c\ub85c \uad6c\ud604\ud55c DFS<\/h1>\n

\n DFS \uc54c\uace0\ub9ac\uc998\uc740 Stack \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud55c\ub2e4.\n<\/p><\/blockquote>\n

\uadf8\ub798\ud504 \ub178\ub4dc\ub97c \uc21c\ud68c\ud558\ub294\ub370 leaf \ub178\ub4dc\uc778 \uc21c\uac04\uae4c\uc9c0 \uc55e\ub9cc \ubcf4\uace0 \ubc29\ubb38\ud55c\ub2e4. \ub9cc\uc57d leaf \ub178\ub4dc\ub97c \ub9cc\ub098\uac8c \ub418\uba74, \uc9c1\uc804\uc758 \ubd84\uae30\uc810\uc73c\ub85c \ub3cc\uc544\uac00 \ub2e4\uc2dc leaf \ub178\ub4dc\ub97c \ub9cc\ub0a0 \ub54c \uae4c\uc9c0 \ubc29\ubb38\ud55c\ub2e4.<\/p>\n

\uc18c\uc2a4\ucf54\ub4dc<\/h2>\n
#!\/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 DFS(graph, root):\n    stack = []\n    visited = []\n    stack.extend(root)\n\n    while(stack):\n        outputFromStack = stack.pop()\n        visited.extend(outputFromStack)\n        inputToStack = list(set(graph[outputFromStack]) - set(visited))\n        inputToStack.sort()\n        stack.extend(inputToStack)\n\n    return visited\n\nprint(DFS(graph, 'A'))\n<\/code><\/pre>\n
\uc218\ud589\uacb0\uacfc<\/h2>\n
$ .\/dfs.py \n['A', 'D', 'I', 'L', 'K', 'H', 'C', 'G', 'B', 'F', 'J', 'E']\n<\/code><\/pre>\n
\uc18c\uc2a4\ucf54\ub4dc \ucd9c\ucc98:
\nhttps:\/\/zetawiki.com\/wiki\/%ED%8C%8C%EC%9D%B4%EC%8D%AC_DFS<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Python\uc73c\ub85c \uad6c\ud604\ud55c DFS DFS \uc54c\uace0\ub9ac\uc998\uc740 Stack \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud55c\ub2e4. \uadf8\ub798\ud504 \ub178\ub4dc\ub97c \uc21c\ud68c\ud558\ub294\ub370 leaf \ub178\ub4dc\uc778 \uc21c\uac04\uae4c\uc9c0 \uc55e\ub9cc \ubcf4\uace0 \ubc29\ubb38\ud55c\ub2e4. \ub9cc\uc57d leaf \ub178\ub4dc\ub97c \ub9cc\ub098\uac8c \ub418\uba74, \uc9c1\uc804\uc758 \ubd84\uae30\uc810\uc73c\ub85c \ub3cc\uc544\uac00 \ub2e4\uc2dc leaf \ub178\ub4dc\ub97c \ub9cc\ub0a0 \ub54c \uae4c\uc9c0 \ubc29\ubb38\ud55c\ub2e4. \uc18c\uc2a4\ucf54\ub4dc #!\/bin\/python graph = {‘A’: [‘B’, ‘C’, ‘D’], ‘B’: [‘A’, ‘E’, ‘F’], ‘C’: [‘A’, ‘G’], ‘D’: [‘A’, ‘H’, ‘I’], ‘E’: [‘B’], ‘F’: [‘B’, […]<\/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-443","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\/443","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=443"}],"version-history":[{"count":4,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/443\/revisions"}],"predecessor-version":[{"id":1288,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/443\/revisions\/1288"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=443"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=443"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=443"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}