[자료구조, 알고리즘] DFS & BFS

1. DFS, BFS 란?

그래프 탐색 알고리즘의 일종

• DFS : 깊이 우선 탐색 - 정점의 자식을 우선적으로 탐색 [스택 이용]
• BFS : 너비 우선 탐색 - 정점과 같은 레벨에 있는 노드를 우선적으로 탐색 [큐 이용]

---

2. DFS - Depth First Search [깊이 우선 탐색]

• 시작 노드를 스택에 삽입하고 방문 표시
• 스택이 비어있지 않으면 노드를 하나 꺼냄
• 꺼낸 노드의 인접 노드를 스택에 넣고 방문표시

* 같은 DFS이지만 방식에 따라 방문 방향이 다를 수 있음에 주의하자.

---

2-1. DFS - 재귀호출

JAVA

graph, visited 는 public static 필드로 두었다.
Collection Framework의 HashMap과 ArrayList를 사용했다.

public void dfsRecursive(String startNode) {
    visited.add(startNode);

    for (String node : graph.get(startNode)) {
        if (!visited.contains(node)) {
            dfsRecursive(node);
        }
    }
}

C++

graph, visited는 public 필드로 두었다.
C++ STL의 map과 vector를 사용했다.

void dfsRecursive(const string& startNode) {
    visited.push_back(startNode);

    for (const string& node : graph[startNode]) {
        if (find(visited.begin(), visited.end(), node) == visited.end()) {
            dfsRecursive(node);
        }
    }
}

python

클래스를 만들어 graph, visited를 필드로 두었다.
graph는 dict() key: str => value: list(), visited는 list()이다.

def dfs_recursive(self, start_node: str):
    self.visited.append(start_node)

    for node in self.graph[start_node]:
        if node not in self.visited:
            self.dfs_recursive(node)

---

2-2. DFS - 반복문

JAVA

public void dfsLoop(String startNode) {
    ArrayList<String> needVisit = new ArrayList<>();

    needVisit.add(startNode);
    while (!needVisit.isEmpty()) {  // 스택이 빌 때까지 진행
        // 끝에서부터 꺼내온다 => 스택
        String node = needVisit.remove(needVisit.size() - 1);

        // 방문하지 않은 노드라면 방문 표시 후 스택에 넣는다.
        if (!visited.contains(node)) {
            visited.add(node);
            needVisit.addAll(graph.get(node));
        }
    }
}

C++

void dfsLoop(const string& startNode) {
    stack<string> needVisit;

    needVisit.push(startNode);
    while (!needVisit.empty()) {
        string node = needVisit.top(); needVisit.pop();
        if (find(visited.begin(), visited.end(), node) == visited.end()) {
            visited.push_back(node);
            for (const string& child : graph[node])
                needVisit.push(child);
        }
    }
}

python

def dfs_loop(self, start_node: str):
    need_visit = list()
    need_visit.append(start_node)

    # 빈 sequence(string, tuple, list)는 false 값을 가진다.
    while need_visit:  
        node = need_visit.pop()
        if node not in self.visited:
            self.visited.append(node)
            need_visit.extend(self.graph[node])

---

3. BFS - Breadth First Search [너비 우선 탐색]

• 시작 노드를 큐에 삽입하고 방문 표시
• 큐가 비어있지 않으면 노드를 하나 꺼냄
• 꺼낸 노드의 인접 노드를 큐에 넣고 방문표시

* 같은 BFS이지만 방식에 따라 방문 방향이 다를 수 있음에 주의하자.
* BFS는 재귀호출과 반복문의 차이가 거의 없다.

---

3-1. BFS - 재귀호출

JAVA

public void bfsRecursive() {
    if (queue.isEmpty()) return;

    String node = queue.poll();
    for (String nextNode : graph.get(node)) {
        if (!visited.contains(nextNode)) {
            visited.add(nextNode);
            queue.add(nextNode);
        }
    }
    bfsRecursive();
}

C++

void bfsRecursive() {
    if (q.empty()) return;

    const auto& startNode = q.front(); q.pop();

    for (const string& node : graph[startNode]) {
        if (find(visited.begin(), visited.end(), node) == visited.end()) {
            visited.push_back(node);
            q.push(node);
        }
    }
    bfsRecursive();
}

python

def bfs_recursive(self):
    if self.queue.empty():
        return

    start_node = self.queue.get()
    for node in self.graph[start_node]:
        if node not in self.visited:
            self.visited.append(node)
            self.queue.put(node)

    self.bfs_recursive()

---

3-2. BFS - 반복문

JAVA

public void bfsLoop(String startNode) {
    queue.add(startNode);
    while (!queue.isEmpty()) {
        // 앞에서부터 꺼내온다 => 큐
        String node = queue.poll();

        for (String nextNode : graph.get(node)) {
            if (!visited.contains(nextNode)) {
                visited.add(nextNode);
                queue.add(nextNode);
            }
        }
    }
}

C++

void bfsLoop(const string& startNode) {
    queue<string> needVisit;

    needVisit.push(startNode);
    while (!needVisit.empty()) {
        string node = needVisit.front(); needVisit.pop();
        if (find(visited.begin(), visited.end(), node) == visited.end()) {
            visited.push_back(node);
            for (const string& child : graph[node])
                needVisit.push(child);
        }
    }
}

python

def bfs_loop(self, start_node: str):
    self.queue.appendleft(start_node)

    while self.queue:  # 빈 sequence(string, tuple, list)는 false 값을 가진다
        node = self.queue.pop()
        if node not in self.visited:
            self.visited.append(node)
            self.queue.extendleft(self.graph[node])