DFS/BFS

코딩 테스트에서 많이 출제되는 알고리즘 중 하나인 DFS와 BFS에 대해 알아보고자 한다.
계속 공부하지만 문제를 풀 때마다 헷갈리기에, 이번 포스팅을 계기로 확실하게 개념을 익히는 것이 목표이다.

🍀 DFS(Depth-First Search, 깊이 우선 탐색)

DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색한다.

[스택 자료구조를 이용한 DFS 동작 과정]

1. 탐색 시작 노드를 스택에 삽입 -> 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리 -> 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복.

[스택을 이용해 재귀함수로 구현한 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)

    # graph : 각 노드가 2차원 리스트로 표현
    # visited : 각 노드의 방문 여부를 1차원 리스트로 표현
    # dfs(그래프, 노드, 방문 리스트) 

 

🍀 BFS(Breadth-First Search, 너비 우선 탐색)

BFS는 가까운 노드부터 탐색하는 알고리즘이다. DFS와는 달리 큐 자료구조를 활용해 구현한다. 인접한 노드를 반복적으로 큐에 넣는 방식으로 작성한다.

[큐 자료구조를 이용한 BFS 동작 과정]

1. 탐색 시작 노드를 큐에 삽입 -> 방문처리
2. 큐에서 노드를 꺼냄 -> 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복.

[deque을 이용해 구현한 BFS]

• deque 라이브러리를 사용하는 것이 좋다.
• 일반적인 경우 실제 수행시간은 DFS보다 좋은 편이다.

    from collections import deque

    def bfs(graph, v, visited):
        queue - dequq([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 : 각 노드가 2차원 리스트로 표현
    # visited : 각 노드의 방문 여부를 1차원 리스트로 표현
    # bfs(그래프, 노드, 방문 리스트)

---

📚 참고 : 이것이 취업을 위한 코딩 테스트다 with 파이썬