DFS 알고리즘 - 하나를 깊게 파는 것도 중요하다구요!

안녕하세요. 오늘은 DFS 알고리즘을 공부하려고 합니다.

저번에 공부한 BFS 알고리즘과 비슷한 궤인데 살펴볼까요?

---

DFS 알고리즘이란

Depth First Search의 약자로 깊이 우선 탐색이라고도 합니다.

DFS 알고리즘의 동작 방식을 간단히 설명드리면 일단 쭈우우욱 갈 수 있는데까지 가본 다음에 다른 길을 살펴보는 탐색법입니다.

 

DFS 알고리즘 pseudo code

pseudo code는 다음과 같습니다.

• 시작 노드와 연결된 모든 노드의 탐색을 하는 코드입니다.

def DFS(graph, start_node_id):
    graph.set_node_visited(start_node_id)
    for connected_node in graph.get_connected_nodes(start_node_id):
        if connected_node.is_visited:
            continue
        DFS(graph, connected_node.id)

 

이제 그림과 함께 살펴보겠습니다!

또 나온 예제 그래프 짜잔!

DFS 알고리즘을 이용해서 노드1에서 탐색을 시작해보겠습니다.

탐색할 노드는 노란색으로 칠했습니다.

DFS 알고리즘을 이용한 노드 탐색 순서

DFS 알고리즘 예제 코드

from dataclasses import dataclass
from typing import List

STAGE = 1

@dataclass
class Node:
    id: int
    is_visited: bool = False

@dataclass
class Edge:
    start_node: Node
    end_node: Node

    def get_other_node(self, node_id: int) -> Node:
        if self.start_node.id == node_id:
            return self.end_node
        else:
            return self.start_node

@dataclass
class Graph:
    nodes: dict
    adjacent_edges: dict

    def get_node(self, node_id: int) -> Node:
        return self.nodes[node_id]

    def set_node_visited(self, node_id: int):
        self.nodes[node_id].is_visited = True

    def get_connected_nodes(self, node_id: int) -> List[Node]:
        adjacent_edges = self.adjacent_edges.get(node_id, [])
        return [edge.get_other_node(node_id) for edge in adjacent_edges]

def DFS(graph: Graph, start_node_id: int):
    global STAGE
    graph.set_node_visited(start_node_id)
    print("탐색 {:d}".format(STAGE))
    print("방문한 노드: {:d}".format(start_node_id))
    print()

    for connected_node in graph.get_connected_nodes(start_node_id):
        if connected_node.is_visited:
            continue
        STAGE += 1
        DFS(graph, connected_node.id)



if __name__ == "__main__":
    nodes = {}
    for i in range(6):
        nodes[i+1] = Node(id=i+1)

    adjacent_edges = {}
    adjacent_edges[1] = [Edge(start_node=nodes[1], end_node=nodes[2])]
    adjacent_edges[1] += [Edge(start_node=nodes[1], end_node=nodes[3])]
    adjacent_edges[2] = [Edge(start_node=nodes[2], end_node=nodes[4])]
    adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[5])]
    adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[6])]
    adjacent_edges[3] = [Edge(start_node=nodes[3], end_node=nodes[4])]
    adjacent_edges[5] = [Edge(start_node=nodes[5], end_node=nodes[6])]

    graph = Graph(nodes=nodes, adjacent_edges=adjacent_edges)
    DFS(graph, 1)

 

실행 결과

짠!

---

DFS 알고리즘은 어떠셨나요?

다음에는 목적지까지의 최단 경로를 구하는 경로 계획 알고리즘을 공부해보려고 합니다.

더 공부하고 싶으신 내용이나 부족한 부분 알려주시면 보완하도록 하겠습니다.

감사합니다 👍