DFS, BFS 개념

 

DFS란?

 

Depth-First Search의 약자로, 깊이 우선 탐색 방법.

 

• 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서(스택에서 하나씩 pop하면서 인접노드 중 방문하지 않은 게 나올 때까지 탐색) 다시 깊숙히 들어가는 방향으로 진행한다.

 

 

#dfs 예제

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

#각 노드가 연결된 정보는 2차원 리스트로 표현
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5], 
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

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

dfs(graph, 1, visited)

 

# 이것이 코딩테스트다 - with 파이썬에서 얼음 얼리기 문제 확인

 

--->

자료구조 중 스택을 이용한다.

자기자신을 계속 호출한다. 함수 자체 반복이 아니라 재귀함수를 여러번 반복해서 돌리면서 구현함.

재귀함수가 더이상 안 돌아가면 메인 코드의 반복문에서 값이 하나 올라가서 다음 탐색을 진행함. 

 

 

BFS란?

Breadth-First Search의 약자로, 넓이 우선 탐색 방법

 

• 임의의 노드에서 시작해서 인접한 노드-->멀리 떨어진 노드 순으로 탐색하는데, 해당 노드의 인접 노드 중 방문하지 않은 모든 노드를 큐에 삽입한다. 그다음 큐에 있는 노드를 하나씩 꺼내면서 인접노드를 방문처리하고 큐에 삽입하는 것을 반복한다. 인접 노드가 없으면 꺼내기만 한다. 남아 있는 노드에 방문하지 않은 인접노드가 없을 때까지 반복. 
• BFS는 재귀함수를 호출하지 않는다. 대신 방문한 노드들을 저장하고 차례대로 꺼낼 수 있는 Queue(Dequeue)를 사용한다.
• 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법으로 탐색한다. 

 

 

#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

#각 노드가 연결된 정보는 2차원 리스트로 표현
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5], 
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

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

bfs(graph, 1, visited)

 

 

# 이것이 코딩테스트다 - with 파이썬에서 미로 탈출 문제 확인

 

---> Dequeue 사용, 함수 자체를 다 반복시키고 메인 코드에서는 그 bfs함수의 리턴값을 출력만 함

 

 

 

 

DFS는 스택

BFS는 큐

둘 다 시간 복잡도는 O(N)이지만 일반적으로 BFS가 DFS보다 좀 더 빠르다.