인프런/딩코딩코 알고리즘

[딩코딩코 2025 코딩테스트 필수 알고리즘] - 18. DFS & BFS

sson-coding 2025. 11. 10. 11:33
본 글은 딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』
강의를 듣고 정리한 내용입니다.
강의와 수업 자료에 수록된 일부 코드와 이미지를 참고하여 발췌·활용하였습니다.
코딩테스트 준비를 체계적으로 하고 싶으시다면, 아래 링크에서 강의를 확인해 보세요
👉 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 보러 가기
본 게시물은 파트너스 활동의 일환으로 작성되었으며, 구매 시 소정의 수수료를 받을 수 있습니다.

DFS & BFS

정렬된 데이터를 이분 탐색하는 것처럼 효율적인 방법이 있는 반면에,
모든 경우의 수를 전부 탐색해야 하는 경우가 있다.

그럴때 끝까지 파고드는 DFS 와 갈라진 모든 경우의 수를 탐색하는 BFS 를 사용하면 된다.

DFS 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구해, 공간을 적게 사용한다.
하지만 최단 경로를 탐색하기 쉽지 않다.

BFS 는 모든 분기되는 수를 다 보고 올 수 있어 최단 경로를 쉽게 찾을 수 있다.
하지만 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고, 모든 걸 보고 오다보니 시간이 더 오래 걸릴 수 있다.

위 그림을 통해 DFS,BFS 가 어떤 순서로 탐색하는지 알아보자.

  • DFS : 1-2-3-4-5-6-7-8-9-10
  • BFS : 1-2-5-9-3-6-8-10-4-7

DFS(Depth First Search)

DFS 는 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조이다.

실행과정은 아래와 같다.

  1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
  2. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
  3. 만약 끝에 도달했다면 리턴한다.

재귀함수로 구현

DFS(node) = node + DFS(node 와 인접하지만 방문하지 않은 다른 node) 로 반복하면된다.

그런데 방문하지 않았다는 조건을 어떻게 알 수 있을까?
이를 위해서 visited 라는 배열에 방문한 노드를 기록해두면 된다.

  1. 루트 노드부터 시작한다.
  2. 현재 방문한 노드를 visited 에 추가한다.
  3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
  4. 2부터 방문한다.

예시를 한 번 보자.

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = [] # 방문한 걸 저장하기 위한 배열

1. 우선 탐색 시작 노드를 1로 잡겠습니다!

2. 현재 방문한 노드인 1을 visited 에 추가합니다. # visited -> [1]

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [2, 5, 9] 입니다. 2 에 방문합니다.

4. 현재 방문한 노드인 2을 visited 에 추가합니다. # visited -> [1, 2]

5. 인접한 노드들인 [1, 3] 에서 방문하지 않은 것들은 [3] 입니다. 3에 방문합니다.

6. 현재 방문한 노드인 3을 visited 에 추가합니다. # visited -> [1, 2, 3]

7. 인접한 노드들인 [2, 4] 에서 방문하지 않은 것들은 [4] 입니다. 4에 방문합니다.

8. 현재 방문한 노드인 4을 visited 에 추가합니다. # visited -> [1, 2, 3, 4]

9. 인접한 노드들인 [3] 에서 방문하지 않은 것들이 없습니다. 7로 돌아갑니다.

7. 인접한 노드들인 [2, 4] 에서 방문하지 않은 것들이 없습니다. 5로 돌아갑니다.

5. 인접한 노드들인 [1, 3] 에서 방문하지 않은 것들이 없습니다. 3로 돌아갑니다.

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [5, 9] 입니다. 5에 방문합니다.

10. 현재 방문한 노드인 5를 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5]

11. 인접한 노드들인 [1, 6, 8] 에서 방문하지 않은 것들은 [6, 8] 입니다. 6에 방문합니다.

12. 현재 방문한 노드인 6를 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6]

13. 인접한 노드들인 [5, 7] 에서 방문하지 않은 것들은 [7] 입니다. 7에 방문합니다.

14. 현재 방문한 노드인 7를 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6, 7]

15. 인접한 노드들인 [6] 에서 방문하지 않은 것들이 없습니다. 11로 돌아갑니다.

11. 인접한 노드들인 [1, 6, 8] 에서 방문하지 않은 것들은 [8] 입니다. 8에 방문합니다.

16. 현재 방문한 노드인 8을 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6, 7, 8]

17. 인접한 노드들인 [5] 에서 방문하지 않은 것들이 없습니다. 11로 돌아갑니다.

11. 인접한 노드들인 [1, 6, 8] 에서 방문하지 않은 것들이 없습니다. 3으로 돌아갑니다.

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [9] 입니다. 9에 방문합니다.

18. 현재 방문한 노드인 9을 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

19. 인접한 노드들인 [1, 10] 에서 방문하지 않은 것들은 [10] 입니다. 10에 방문합니다.

20. 현재 방문한 노드인 10을 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

21. 인접한 노드들인 [9] 에서 방문하지 않은 것들이 없습니다. 19로 돌아갑니다.

19. 인접한 노드들인 [1, 10] 에서 방문하지 않은 것들이 없습니다. 3로 돌아갑니다.

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들이 없습니다. 1로 돌아갑니다.

1. 끝났습니다.

위 내용을 코드로 구현해보자.

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []

def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph[cur_node]:
        if adjacent_node not in visited_array:
            dfs_recursion(adjacent_graph,adjacent_node,visited_array)

dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)

스택으로 구현

재귀함수를 통해 구현했을 경우 무한정 깊어지는 노드가 있는 경우 RecursionError 에러가 발생할 수 있다.

그러면 다른 방법으로 해결할 수 있을까?

DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다.
이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,
가장 마지막에 넣은 노드들만 꺼내서 탐색하면 된다.

  1. 루트 노드를 스택에 넣는다.
  2. 현재 스택의 노드를 빼서 visited 에 추가한다.
  3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
  4. 2부터 반복한다.
  5. 스택이 비면 탐색을 종료한다.

예시를 살펴보자.

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = [] # 방문한 걸 저장하기 위한 배열
stack = [1] # 시작 노드인 1을 넣어둔다.

1. 현재 스택에서 가장 마지막에 넣은 1을 빼서, visited 에 추가합니다. 
# stack -> [] visited -> [1]

2. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들인 [2, 5, 9]를 stack 에 추가합니다. 
# stack -> [2, 5, 9] visited -> [1]

3. 현재 스택에서 가장 마지막에 넣은 9을 빼서, visited 에 추가합니다. 
# stack -> [2, 5] visited -> [1, 9]

4. 인접한 노드들인 [1, 10] 에서 방문하지 않은 것들인 [10] 을 stack 에 추가합니다. 
# stack -> [2, 5, 10] visited -> [1, 9]

5. 현재 스택에서 가장 마지막에 넣은 10을 빼서, visited 에 추가합니다. 
# stack -> [2, 5] visited -> [1, 9, 10]

6. 인접한 노드들인 [9] 에서 방문하지 않은 노드들이 없으니 추가하지 않습니다.
# stack -> [2, 5] visited -> [1, 9, 10]

7. 현재 스택에서 가장 마지막에 넣은 5를 빼서, visited 에 추가합니다. 
# stack -> [2] visited -> [1, 9, 10, 5]

8. 인접한 노드들인 [1, 6, 8] 에서 방문하지 않은 것들인 [6, 8]를 stack 에 추가합니다. 
# stack -> [2, 6, 8] visited -> [1, 9, 10, 5]

9. 현재 스택에서 가장 마지막에 넣은 8를 을 빼서, visited 에 추가합니다. 
# stack -> [2, 6] visited -> [1, 9, 10, 5, 8]

10. 인접한 노드들인 [5] 에서 방문하지 않은 노드들이 없으니 추가하지 않습니다.
# stack -> [2, 6] visited -> [1, 9, 10, 5, 8]

11. 현재 스택에서 가장 마지막에 넣은 6을 빼서, visited 에 추가합니다. 
# stack -> [2] visited -> [1, 9, 10, 5, 8, 6]

12. 인접한 노드들인 [5, 7] 에서 방문하지 않은 것들인 [7] 을 stack 에 추가합니다. 
# stack -> [2, 7] visited -> [1, 9, 10, 5, 8, 6]

13. 현재 스택에서 가장 마지막에 넣은 7를 을 빼서, visited 에 추가합니다. 
# stack -> [2] visited -> [1, 9, 10, 5, 8, 6, 7]

14. 인접한 노드들인 [6] 에서 방문하지 않은 노드들이 없으니 추가하지 않습니다.
# stack -> [2] visited -> [1, 9, 10, 5, 8, 6, 7]

15. 현재 스택에서 가장 마지막에 넣은 2를 빼서, visited 에 추가합니다. 
# stack -> [] visited -> [1, 9, 10, 5, 8, 6, 7, 2]

16. 인접한 노드들인 [1, 3] 에서 방문하지 않은 것들인 [3] 을 stack 에 추가합니다. 
# stack -> [3] visited -> [1, 9, 10, 5, 8, 6, 7, 2]

17. 현재 스택에서 가장 마지막에 넣은 3을 빼서, visited 에 추가합니다. 
# stack -> [] visited -> [1, 9, 10, 5, 8, 6, 7, 2, 3]

18. 인접한 노드들인 [2, 4] 에서 방문하지 않은 것들인 [4] 를 stack 에 추가합니다. 
# stack -> [4] visited -> [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]

19. 현재 스택에서 가장 마지막에 넣은 4를 빼서, visited 에 추가합니다. 
# stack -> [] visited -> [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]

20. 인접한 노드들인 [3] 에서 방문하지 않은 노드들이 없으니 추가하지 않습니다.

21. 현재 스택에서 꺼낼 것이 없습니다. DFS 가 끝났습니다.

재귀로 구현했을 때와 탐색하는 순서가 다르지만 가장 깊게 탐색하는 방식은 똑같다.

위 내용을 코드로 구현해보자.

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited=[]
    while stack:
        current_node = stack.pop()
        visited.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)

    return visited

print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!

BFS(Breadth First Search)

BFS 는 현재 인접한 노드를 먼저 방문해야 한다.

이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고
가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.

가장 처음에 넣은 노드들 → 큐를 이용하면 BFS 를 구현할 수 있다.

구현 방법은 다음과 같다.

  1. 루트 노드를 큐에 넣는다.
  2. 현재 큐의 노드를 빼서 visited 에 추가한다.
  3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
  4. 2부터 반복한다.
  5. 큐가 비면 탐색을 종료한다.

예시를 통해 살펴보자.

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}
visited = [] # 방문한 걸 저장하기 위한 배열
queue = [1] # 시작 노드인 1을 넣어둔다.

1. 현재 큐에서 가장 처음에 넣은 1을 빼서, visited 에 추가합니다. 
# queue -> [] visited -> [1]

2. 인접한 노드들인 [2, 3, 4] 에서 방문하지 않은 것들인 [2, 3, 4]를 queue 에 추가합니다. 
# queue -> [2, 3, 4] visited -> [1]

3. 현재 큐에서 가장 처음에 넣은 2을 빼서, visited 에 추가합니다. 
# queue -> [3, 4] visited -> [1, 2]

4. 인접한 노드들인 [1, 5] 에서 방문하지 않은 것들인 [5]를 queue 에 추가합니다. 
# queue -> [3, 4, 5] visited -> [1, 2]

5. 현재 큐에서 가장 처음에 넣은 3을 빼서, visited 에 추가합니다. 
# queue -> [4, 5] visited -> [1, 2, 3]

6. 인접한 노드들인 [1, 6, 7] 에서 방문하지 않은 것들인 [6, 7]를 queue 에 추가합니다. 
# queue -> [4, 5, 6, 7] visited -> [1, 2, 3]

7. 현재 큐에서 가장 처음에 넣은 4을 빼서, visited 에 추가합니다. 
# queue -> [5, 6, 7] visited -> [1, 2, 3, 4]

8. 인접한 노드들인 [1, 8] 에서 방문하지 않은 것들인 [8]를 queue 에 추가합니다. 
# queue -> [5, 6, 7, 8] visited -> [1, 2, 3, 4]

9. 현재 큐에서 가장 처음에 넣은 5을 빼서, visited 에 추가합니다. 
# queue -> [6, 7, 8] visited -> [1, 2, 3, 4, 5]

10. 인접한 노드들인 [2, 9] 에서 방문하지 않은 것들인 [9]를 queue 에 추가합니다. 
# queue -> [6, 7, 8, 9] visited -> [1, 2, 3, 4, 5]

11. 현재 큐에서 가장 처음에 넣은 6을 빼서, visited 에 추가합니다. 
# queue -> [7, 8, 9] visited -> [1, 2, 3, 4, 5, 6]

12. 인접한 노드들인 [3, 10] 에서 방문하지 않은 것들인 [10]를 queue 에 추가합니다. 
# queue -> [7, 8, 9, 10] visited -> [1, 2, 3, 4, 5, 6]

13. 현재 큐에서 가장 처음에 넣은 7을 빼서, visited 에 추가합니다. 
# queue -> [8, 9, 10] visited -> [1, 2, 3, 4, 5, 6, 7]

14. 인접한 노드들인 [3] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [8, 9, 10] visited -> [1, 2, 3, 4, 5, 6, 7]

15. 현재 큐에서 가장 처음에 넣은 8을 빼서, visited 에 추가합니다. 
# queue -> [9, 10] visited -> [1, 2, 3, 4, 5, 6, 7, 8]

16. 인접한 노드들인 [4] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [9, 10] visited -> [1, 2, 3, 4, 5, 6, 7, 8]

17. 현재 큐에서 가장 처음에 넣은 9을 빼서, visited 에 추가합니다. 
# queue -> [10] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

18. 인접한 노드들인 [5] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [10] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

19. 현재 큐에서 가장 처음에 넣은 10을 빼서, visited 에 추가합니다. 
# queue -> [] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

20. 인접한 노드들인 [6] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

21. 현재 큐에서 꺼낼 것이 없습니다. BFS 가 끝났습니다.

위 내용을 코드로 구현해보자.

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}

def bfs_queue(adj_graph, start_node):
    queue = deque([start_node])
    visited=[]

    while queue:
        current_node = queue.popleft()
        visited.append(current_node)
        for adjacent_node in adj_graph[current_node]:
            if adjacent_node not in visited:
                queue.append(adjacent_node)

    return visited

print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

'인프런 > 딩코딩코 알고리즘' 카테고리의 다른 글

[딩코딩코 2025 코딩테스트 필수 알고리즘] - 20. LINE 인턴 채용 코딩테스트 - 나 잡아 봐라  (0) 2025.11.19
[딩코딩코 2025 코딩테스트 필수 알고리즘] - 19. Dynamic Programming  (0) 2025.11.19
[딩코딩코 2025 코딩테스트 필수 알고리즘] - 17. 그래프  (0) 2025.11.10
[딩코딩코 2025 코딩테스트 필수 알고리즘] - 16. 힙  (0) 2025.11.10
[딩코딩코 2025 코딩테스트 필수 알고리즘] - 15.트리  (0) 2025.11.02

'인프런/딩코딩코 알고리즘'의 다른글

  • 현재글[딩코딩코 2025 코딩테스트 필수 알고리즘] - 18. DFS & BFS

관련글

티스토리툴바