[알고리즘] DFS, BFS

알고리즘

[알고리즘] DFS, BFS

songsua 2025. 2. 24. 00:54

DFS란?

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색하고 끝까지 탐색하면 다시 위로 와서 다음을 탐색함여 검색한다.

BFS란?

한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다.

왜 사용하는 걸까?

모든 경우의 수를 전부 탐색해야할 경우에 쓰인다. 예시로 알파고가 있다.

모든 대국의 수를 계산하고 예측하여 최적의 수를 계산해내기 위해 모든 수를 전부 탐색해야 한다.

DFS 와 BFS 는 그 탐색하는 순서에서 차이가 있다.

DFS는 끝까지 파고드는 것이고 BFS는 갈라진 모든 경우의 수를 탐색해보고 오는 것이다.

실제 구현해보기

DFS

- 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.

- 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.

- 만약 끝에 도달했다면 리턴한다.

즉, 깊이를 우선 깊게 들어간 후에 끝이 날 경우 1번과 근접한 노드 중 방문하지 않은 노드로 반복하여 방문하는 것

방문하지 않은 노드라는 것을 어떻게 알 수 있을까?

이는 visited라는 배열에 방문한 노드를 기록해 두면 될 것이다.

예시코드

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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. 현재 방문한 노드를 visiteed_array 에 추가한다
#3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 방문한다.

def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    print(adjacent_graph[cur_node])
    print("visited_array : " , visited_array)
    #하나하나 꺼내본 다음에 visited 배열에 없다면, dfs_recursion 함수를 호출하여, 2,3의 행위를 반복한다.
    for i in adjacent_graph[cur_node] :
        print("i = " , i)
        if i not in visited: #방문하지 않았다면
            dfs_recursion(adjacent_graph, i , visited_array)
        
    return
dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

그러나, 이런식으로 무한정 깊어지는 노드가 있는 경우에는 에러가 발생할 수 있다.

탈출 조건없이 반복하다보면 RecursionError라는 것이 발생할 수 있기 때문이다.

따라서 다른 방법으로 해결해야한다.

가장 마지막에 넣은 노드들을 꺼내서 탐색만 하면되는데 이는 스택을 이용하면 DFS 를 재귀 없이 구현할 수 있다.

1. 루트 노드를 스택에 넣는다

2. 현재 스택의 노드를 빼서 visited에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다

4. 2번부터 반복한다

5. 스택이 비면 탐색을 종료한다.

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]
}

#1. 시작 노드를 스택에 넣는다.
#2. 현재 스택의 노드를 빼서 visited 에 추가한다.
#3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
#위의 과정을 스택이 빌 때까지 반복한다.

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visted = []
    print("현재 스택에 있는 것 = " , stack )
    
    while stack : 
       current_node = stack.pop()
       visted.append(current_node)
       print("current_node = " , current_node)
       #3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
       for i in adjacent_graph[current_node] :
           print("현재 노드와 연관된 노드들 = " , i , "방문한 적 있는 노드들 : " , visted )
           if i not in visted :
               stack.append(i)
               print("stack에 들어가 있는 것들 = " , stack)
            

    return visted


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

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 가 끝났습니다.

큐를 사용하기 위해서 deque를 사용한다

from collections import deque

deq = deque()

# Add element to the start
deq.appendleft(10)

# Add element to the end
deq.append(0)

# Pop element from the start
deq.popleft()

# Pop element from the end
deq.pop()

deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
deque.remove(item): item을 데크에서 찾아 삭제한다.
deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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]
}

#1.시작 노드를 큐에 넣는다
#2. 큐에 노드를 빼서 visited에 넣는다
#3. 현재 방문한 노드와 인접한 노드 중 방문하지 않는 노드를 큐에 추가한다
#4. 2~3번의 과정을 큐가 빌 때까지 반복한다.
#queue 를 사용하기 위해서 deque로 함으로써 큐로 사용할 수 있게 한다.

def bfs_queue(adj_graph, start_node):
    que = deque([start_node])
    visited = []
    
    while que :
        current_node = que.popleft()
        print("현재 방문한 노드 : " , current_node)
        visited.append(current_node)
        for i in adj_graph[current_node] :
            print("현재 노드에서 인접한 애들을 출력 =" , i)
            if i not in visited :
                que.append(i)

    return visited


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

현재 방문한 노드 :  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
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

'알고리즘' 카테고리의 다른 글

[알고리즘] Dynamic Programming (0)	2025.02.24
[알고리즘] 그래프 (0)	2025.02.23
[알고리즘] 트리, 힙 (0)	2025.02.23
[알고리즘] 점근 표기법 (0)	2025.02.23
[알고리즘] 1주차 시간 복잡도 & 공간복잡도 (0)	2025.02.22

현재글[알고리즘] DFS, BFS

배고프지만 공부

뭐든 적어보는

추상메서드, Java, 코테, 알고리즘, java중급, 회원가입 백엔드 구축, 스프링, 중급자바, 스프링기초, 백엔드, slq, SQL, SQLP, 자바, 익명클래스, 메서드, 김영한, slqp, 코딩테스트, 향해99,

Today :
Yesterday :

배고프지만 공부