DFS/BFS / 재귀

DFS/BFS / 재귀

https://www.youtube.com/watch?v=7C9RgOcvkvo&list;=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index;=3

https://github.com/ndb796/python-for-coding-test -->코드 깃허브

자바에서의 덱 사용 방법

파이썬 덱

from collections import deque # 큐 구현할때는 효율이 좋은 덱 이용하기 queue = deque() # append, popleft, reverse # <--나가는 방향 --<---들어오는방향

DFS/BFS를 위해서는 재귀함수를 불가피하게 사용하는 경우가 발생한다.

def recursive_function(i): if i==100: return print(i,"번째") recursive_function(i+1) print(i,'번째 종료') recursive_function(1)

실행 결과:

1 번째 2 번째 3 번째 4 번째 5 번째 ..... 95 번째 96 번째 97 번째 98 번째 99 번째 99 번째 종료 98 번째 종료 97 번째 종료 96 번째 종료 95 번째 종료 94 번째 종료 ... 5 번째 종료 4 번째 종료 3 번째 종료 2 번째 종료 1 번째 종료

# DFS

dfs 재귀함수

def dfs(graph, v, vsited): # 현재 노드를 방문 처리 visited[v] = True print(v,end=' ') for i in graph[v]: if not visited[i]: dfs(graph,i,visited)

graph =[ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited=[False]*9 dfs(graph,1,visited)

실행결과 : 1 2 7 6 8 3 4 5

# BFS

from collections import deque def bfs(graph, start, visited): queue = deque([start]) visited[start]=True while queue: v=queue.popleft() print(v, end=' ') for i in graph[v]: if not visited[i]: queue.append(i) visited[i]=True

from http://ccssbb.tistory.com/519 by ccl(A) rewrite - 2021-11-23 02:01:06