BFS, DFS

bfs, dfs 얘기를 하기 전 기본 그래프 알고리즘에 대해 살펴보겠습니다.

 

 

그래프 알고리즘?

그래프 알고리즘은 실제 세계의 다양한 문제를 모델링하고 해결하는데 필수적인 도구입니다.
사람들 간의 소셜 네트워크, 웹페이지의 링크 구조, 도로 네트워크의 복잡한 관계 표현.

물류, 통신, 교통의 경로 문제 해결등 다양한 분야에서 중요한 역할을 수행하며, 이를 통해 우리는 복잡한 문제를 효과적으로 해결할 수 있습니다.

 

그렇다면 컴퓨터에서 그래프를 어떻게 표현할까요?

인접행렬과 인접리스트를 사용해 표현합니다.

 

어떻게 표현하는지 알았으니 인접행렬과 인접리스트를 어떻게 들여다볼까요?

여기서 그래프 알고리즘이 사용됩니다. 

 

기본적인 그래프 알고리즘은 

 

1. 너비 우선 탐색(BFS, Breadth-First Search):

BFS는 그래프의 모든 노드를 방문하는 방법 중 하나로, 시작 노드에서 가장 가까운 노드를 먼저 방문한 후, 그다음으로 가까운 노드를 방문하는 방식입니다. BFS는 큐(Queue)라는 자료구조를 사용하여 구현할 수 있습니다.

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

DFS는 그래프의 모든 노드를 방문하는 또 다른 방법으로, 시작 노드에서 가장 멀리 있는 노드를 먼저 방문하려는 경향이 있습니다. DFS는 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다.

 

3. 최단 경로 알고리즘:

이 알고리즘은 시작 노드에서 다른 노드까지의 최단 경로를 찾는 문제를 해결하는 데 사용됩니다. 대표적인 최단 경로 알고리즘으로는 다익스트라 알고리즘(Dijkstra's algorithm), 벨만-포드 알고리즘(Bellman-Ford algorithm), 플로이드-워셜 알고리즘(Floyd-Warshall algorithm) 등이 있습니다.

 

이 중 너비우선탐색(BFS)과 깊이 우선 탐색(DFS)에 대해 살펴보겠습니다. 

 

BFS?

너비 우선 탐색은 가장 단순한 그래프 알고리즘 중 하나로, 중요한 그래프 알고리즘들의 원형(archetype)입니다. 

위에서 방법에 대해 말했으니 탐색 순서에 대해 알아보겠습니다. 

 

1. 시작 노드를 큐에 넣습니다.
2. 큐에서 노드를 꺼냅니다. 꺼낸 노드가 탐색 대상이면 탐색을 종료합니다.
3. 꺼낸 노드를 방문했다는 표시를 합니다.
4. 꺼낸 노드에 연결된 노드들 중에서 아직 방문하지 않은 노드를 큐에 넣습니다.
5. 큐가 비어있지 않다면 2번으로 돌아가서 반복합니다. 큐가 비어있다면 모든 노드를 방문한 것이므로 탐색을 종료합니다.

 

파이썬 코드입니다. 

def bfs(graph, start):  # bfs 함수를 정의합니다. 인자로는 그래프와 시작 노드를 받습니다.
    visited = []  # 방문한 노드들을 저장할 리스트를 초기화합니다.
    queue = deque([start])  # 탐색을 시작할 노드를 큐에 넣습니다.

    while queue:  # 큐가 비어있지 않는 동안 반복합니다.
        node = queue.popleft()  # 큐에서 노드를 하나 꺼냅니다.
        if node not in visited:  # 꺼낸 노드가 아직 방문한 적 없는 노드라면
            visited.append(node)  # 방문한 노드 리스트에 추가합니다.
            queue.extend(graph[node] - set(visited))  # 해당 노드의 인접 노드 중 방문하지 않은 노드들을 큐에 추가합니다.
    return visited  # 모든 노드를 방문하면 방문한 노드 리스트를 반환합니다.

 

BFS(너비 우선 탐색)는 

최단 경로 찾기: BFS는 무방향 그래프에서 한 점에서 다른 점까지의 최단 경로를 찾는 데 사용됩니다. 이때의 '최단'은 가장 적은 수의 엣지를 통과하는 경로를 의미합니다.
그래프의 연결성 파악: BFS를 사용하면 그래프의 모든 노드를 방문할 수 있으므로, 그래프의 모든 부분이 서로 연결되어 있는지, 또는 특정 노드가 그래프에 포함되어 있는지 확인하는 데 사용될 수 있습니다.

 

 

DFS?

 

BFS(너비 우선 탐색)가 노드를 방문할 때 해당 노드의 인접 노드를 먼저 방문하는 반면, DFS는 노드를 방문할 때 가능한 한 깊숙이 들어가서 노드를 방문합니다.

DFS는 다음과 같은 순서로 진행됩니다:

1. 시작 노드를 방문하고, 그 노드를 스택에 넣습니다.
2. 현재 스택의 맨 위 노드에서 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 방문하고 스택에 넣습니다. 방문하지 않은 인접 노드가 없으면 스택에서 해당 노드를 제거합니다.
3. 스택이 비어있을 때까지 2번 과정을 반복합니다.

 

def dfs(graph, start):  # dfs 함수를 정의합니다. 인자로는 그래프와 시작 노드를 받습니다.
    visited = []  # 방문한 노드들을 저장할 리스트를 초기화합니다.
    stack = [start]  # 탐색을 시작할 노드를 스택에 넣습니다.

    while stack:  # 스택이 비어있지 않는 동안 반복합니다.
        node = stack.pop()  # 스택에서 노드를 하나 꺼냅니다.
        if node not in visited:  # 꺼낸 노드가 아직 방문한 적 없는 노드라면
            visited.append(node)  # 방문한 노드 리스트에 추가합니다.
            stack.extend(graph[node] - set(visited))  # 해당 노드의 인접 노드 중 방문하지 않은 노드들을 스택에 추가합니다.
    return visited  # 모든 노드를 방문하면 방문한 노드 리스트를 반환합니다.

DFS는 그래프의 모든 노드를 방문하는 것을 보장하며, 경로 탐색, 사이클 검출, 트리나 그래프의 연결성 체크 등 다양한 문제를 해결하는 데 사용될 수 있습니다. 또한, 미로 찾기, 백트래킹(Backtracking) 기법 등에도 활용됩니다.

그러나 DFS는 최단 경로를 찾는 문제에는 적합하지 않으며, 이 경우 BFS를 사용하는 것이 더 효율적일 수 있습니다.