[Algorithm] DFS/BFS - 1

스택 - 선입후출 (처음에 들어간게 제일 나중에 나옴) --> pop() 사용, append()로 스택에 입력 가능

큐 - 선입선출 --> popleft() 사용, append()로 큐에 입력 가능

큐 사용시 deque 사용

[예제]

from collections import deque

queue = deque() ## deque 라이브러리 사용

queue.reverse() ## 큐를 역순으로 바꾸기

## 해당 코드는 기본적으로 외워 놓는 것이 좋음

 

근데 리스트로 선언해도 됨!!

 

DFS (Depth-First Search, 깊이 우선 탐색)

위와 같은 트리가 있다는 가정하에, DFS가 동작한다면 어떻게 동작할 까?

- DFS는 순서와 상관없이 처리해도 됨

- 코딩 테스트에서는 번호가 낮은 순서부터 처리하도록 명시하는 경우가 있음 (일반적으로 번호가 낮은 순서부터 처리하도록 구현)

결과 예시 : 1,2,7,6,8, 3,4,5

 

일단 한 쪽을 깊이 끝까지 파헤친 후에, 다음 깊이를 찾아 감

재귀 함수로 이용해서 실행

def dfs(graph, v, visited):

    visited[v] = True ## 먼저, 해당 노드 방문 확인
    print(v, end = ' ')
    for i in graph[v]: # 노드와 연관된 다른 노드들 확인
        if not visited[i]: # 방문하지 않았다면
            dfs(graph, i, visited) # 재귀 함수 실행



graph = [
    [],
    [2,3,8], # 1의 노드에는 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)

재귀 함수 코드는 쉬우니깐 외우자