DFS/BFS / 재귀

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

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

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

---

자바에서의 덱 사용 방법

파이썬 덱

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