[이코테][Chapter 5]DFS, BFS

재귀 : 하나의 함수를 n,n-1,n-2,... 인자를 바꾸어가며 반복하는 것을 의미한다. "스택" 형태로 작용한다.

 

스택 : 선입후출. 상자 쌓기와 동일

큐 : 선입선출. 에스컬레이터와 동일

그래프 : 노드끼리 연결 관계를 표현한 자료형을 의미

DFS : 그래프에서, 한 노드를 계속 파고들면서 탐색하는 방식. 위의 그래프에서는 A-B-C-D-... 순이 된다.

def dfs(graph, v, visited):
    #현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    #현재 노드와 연결된 다른 노드르 재귀적으로 방문
    for i in graph[v]: #그래프 1번 노드 시작. 2,3,8 방문
        if not visited[i]: #방문하지 않았다면?
            dfs(graph, i, visited) #그 노드에서 다시 확인.

graph = [
    [], #0번 노드와 인접한 노드.
    [2,3,8], #1번 노드와 인접한 노드.
    [1,7], #2번
    [1,4,5], #3번
    [3,5], #4번
    [3,4], #5번
    [7], #6번
    [2,6,8], #7번
    [1,7] #8번
    ]

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 # 0번 노드~8번 노드. 총 9개

#정의된 DFS 함수 호출
dfs(graph, 1, visited) #그래프, 시작 노드, 방문 정보

BFS : 그래프에서, 한 노드와 연결된 노드를 탐색하면서 넓어지는 형태로 탐색하는 방식. 위의 그래프에서는 A-B-E-I-... 순이 된다.

from collections import deque

def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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

graph = [
    [], #0번 노드와 인접한 노드.
    [2,3,8], #1번 노드와 인접한 노드.
    [1,7], #2번
    [1,4,5], #3번
    [3,5], #4번
    [3,4], #5번
    [7], #6번
    [2,6,8], #7번
    [1,7] #8번
    ]

visited = [False] * 9

bfs(graph, 1, visited)

 

일반적으로, DFS보단 BFS가 더 빠르다.