Python

DFS / BFS 예제 구현해보기 - python

나른한코딩 2021. 8. 13. 17:42

오늘은 DFS와 BFS의 예제를 구현해보며 로직을 이해해보고자 합니다.

 

DFS와 BFS를 구현하려다보니, 그래프를 먼저 구현하는 해야겠더라구요🤔 

그런데 그래프를 어떻게 구현해야할지 몰라서

우선은 하드코딩으로 그래프를 생성한 후, DFS / BFS를 구현해보았습니다.

 

다음 글에 그래프 구현에 대한 글을 올려두겠습니다 😄

 

DFS와 BFS의 개념을 간단하게 소개한 후 바로 코드로 넘어가겠습니다.

.

.

.

.

그래프를 탐색하는 방법에는 크게 DFS와 BFS가 있습니다.

1. DFS (Depth-First Search)

'깊이우선탐색(DFS)'은 가장 깊은 노드까지 내려단 뒤,

더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하여 탐색을 합니다.

root 노드(혹은 다른 임의의 노드)에서 시작하여 다른 branch로 넘어가기 전에 해당 branch를 전부 탐색하는 방식을 말합니다.

 

🤔 어떨 때 사용하는가?

주로 모든 노드를 방문하고자 하는 경우에 사용됩니다.

대표적으로는

  • 미로 찾기
  • 그래프의 위상 정렬
  • 모든 경우 다 해보기(전체 탐색)
  • 연결 구성 요소 찾기
  • 이분 그래프

문제를 풀 때 사용됩니다.

어떻게 구현?

stack 또는 재귀함수를 사용하여 구현합니다.

(인접행렬, 인접리스트를 사용하여 구현하는 방법도 있으니 추가적으로 실습해보시길 바래요!)

 

 

 

2. BFS(Breath-First Search)

'너비우선탐색(BFS)'는 root노드에서 인접한 노드를 먼저 탐색하는 방법입니다.

따라서 시작 정점으로부터 가장 가까운 정점을 먼저 방문하고,

멀리 떨어져 있는 정점은 나중에 방문하는 식으로 탐색하는 방식을 말합니다.

 

🤔  어떨 때 사용하는가?

주로 최단 경로 문제에서 사용됩니다.

대표적으로는

  • 두 정점 u,v 간의 최단 경로 찾기( 경로의 길이는 간선의 수에 따라 정해질 때)
  • 문자열 알고리즘 Aho-Corasick 패턴 매칭(순위다중패턴매칭)의 실패함수를 구축할 때
  • 그래프에서 정점들이 두 개의 독립적인 서로소 그룹으로 나누어질 수 있는가에 대해 이분성 테스트를 할 때
  • copying garbage collection
  • cheney's algorithm

문제를 풀 때 사용됩니다.

 

어떻게 구현?

queue를 사용하여 구현합니다.

.

.

.

.

.

.

Let's Code!

우선은 다음과 같이 dictionary로 그래프를 하나 만들어줘 볼게요 !

myGraph = {
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H', 'K'],
    'K': ['J', 'L'],
    'L': ['K'],
    'M': ['H']
}

위의 그래프를 그림으로 표현해보면 다음과 같겠네요.

dfs bfs graph 도식화

(그림 퀄리티는 죄송..)

 

여기서 dfs 를 수행한다면, 

G -> D ->  C -> B -> A -> H -> I -> J -> K -> L -> M -> E -> F
bfs를 수행한다면,

G -> D -> C -> E -> B -> F -> A -> H -> I -> J -> M -> K -> L

이 되겠네요!

 

그러면 본격적으로 코드를 작성해보고 다음과 같이 결과가 나오는 지 해봅시다!

.

.

.

.

DFS 코드는 다음과 같습니다.

def my_dfs(graph, start_node):
    visited = list() # 방문한 노드를 담을 배열
    stack = list() # 정점과 인접한 방문 예정인 노드를 담을 배열

    stack.append(start_node) # 처음에는 시작 노드 담아주고 시작하기.

    while stack: # 더 이상 방문할 노드가 없을 때까지.
        node = stack.pop() # 방문할 노드를 앞에서 부터 하나싹 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            stack.extend(graph[node]) # 해당 노드의 자식 노드로 추가
            # stack.extend(reversed(graph[node]))

    print("dfs - ", visited)
    return visited
    
    # 함수 실행
    my_dfs(myGraph, 'G')

실행해보면?

.

.

.

.

dfs python

오잉 뭔가 순회 순서가 이상하죠?

우리 예상은

G -> D ->  C -> B -> A -> H -> I -> J -> K -> L -> M -> E -> F 
이거였는데🤔

 

그 이유는 우리가 탐색을 왼쪽부터 할 거라는 가정하에 순회 순서를 예상했는데,

위의 코드 상에서는 오른쪽부터 탐색을 했기 때문이에요.

 

따라서 저기 주석처리한 부분으로 코드를 바꾸어 왼쪽부터 순회하게 해주면

.

.

.

.

dfs python reverse

짜잔!
예상한 것과 똑같게 잘 순회한 것을 볼 수 있습니다ㅎㅎ

 

 

이번엔 BFS코드를 작성해볼까요?

def my_bfs(graph, start_node):
    visited = list() # 방문한 노드를 담을 배열
    queue = list() # 방문 예정인 노드를 담을 배열

    queue.append(start_node) # 처음에는 시작 노드 담아주고 시작하기.

    while queue: # 더 이상 방문할 노드가 없을 때까지.
        node = queue.pop(0) # 방문할 노드를 앞에서 부터 하나싹 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            queue.extend(graph[node]) # 해당 노드의 자식 노드로 추가
    
    print("bfs - ", visited)
    return visited
    
    # 함수 실행
    my_bfs(myGraph, 'G')

실행해보면

.

.

.

.

bfs python

우리가 예상한 대로

G -> D -> C -> E -> B -> F -> A -> H -> I -> J -> M -> K -> L

순서로 잘 순회한 것을 볼 수 있습니다~

 

 

'방문예정인 배열'이라는 부분이 잘 이해가 안된다면,

stack과 queue를 각각 print 해보면 알 수 있습니다.

 

우선 DFS를 구현할 때의 stack을 node와 함께 프린트 해볼게요

 

dfs stack

DFS의 탐색 과정을 보면, 

1 - 시작 정점을 먼저 stack[0]에 넣어줍니다.

2 - 그리고 스택에서 가장 위(top)에 있는 원소를 하나 꺼냅니다.

3 - 그 원소를 방문표시(visited)하고, 그 원소와 인접한 정점들 중에서 방문하지 않은 정점들을 모두 스택에 넣습니다.

4 - 방문의 우선순위에 따라 인접한 정점이 여러 개면 번호(알파벳이)가 작은 순서대로 방문해야 하므로, 순서에 맞게 스택에 넣어줍니다.

5 - 계속해서 스택의 가장 위에 있는 원소를 꺼내 방문표시하고, 해당 원소와 인접한 원소 중 방문하지 않은 원소들을 모두 스택에 넣어주는 과정을 반복합니다.

 

 

다음으로 BFS를 구현할 때의 queue를 node와 함께 프린트 해볼게요

bfs queue

BFS의 탐색 과정을 보면,

1 - 시작 정점을 먼저 queue[0]에 추가해 줍니다.

2 - queue에서 제일 앞에 있는 원소를 하나 꺼냅니다.(pop)

3 - 그 원소를 방문표시(visited)하고, 그 원소와 인접한 정점들 중 방문완료되지 않았고, queue에 추가되지 않은 인접한 원소들을 queue에 추가해줍니다.

4 - queue가 빌때까지 반복합니다.

 

⚠️ 주의사항 ⚠️

DFS를 구현할 때는 방문한 노드를 확실하게 확인해주지 않으면 무한루프에 빠질 수 있다는 점 잘 기억하시고 작성하세요!

 

DFS / BFS 비교

DFS는 BFS보다 조금 더 간단하게 구현할 수 있습니다.

검색 속도는 DFS가 BFS에 비해 느립니다.

 

그 이유는

dfs의 경우 모든 노드를 방문하기 떄문입니다!

 

짧은 코드이지만, bfs=0.069s, df=0.07s 로 bfs가 조금 더 빠르네요 🤔

 

둘 중 

어떤 것을 사용해야 하는가?

이 부분은 상황에 따라 다를 것 같네요.

 

위에 작성한 문제들의 목록을 보고 판단하시면 될 것 같습니다.

예시를 하나씩 들자면,

bfs는 최단 거리 문제에 효율적이고, dfs는 이동한 정점의 값을 가지고 계속 연산하는 경우(재귀호출) 에 효율적입니다.

.

.

.

.

지금까지 간단한 예제를 통해 DFS와 BFS 구현 방법을 알아보았습니다.

저는 DFS와 BFS를 그저

DFS는 가장 안쪽까지 먼저 탐색하고 옆으로 넘어간다.

BFS는 같은 레벨에 있는 것들 먼저 탐색하고 다음 레벨로 넘어간다.

 

이정도로만 이해하고 있었어서

이런 기초 예제도 이해하는데 오래걸렸습니다ㅠ,ㅠ

 

저 같으신 분들이 많을 거라 생각하고...한번 글을 작성해보았습니다!

 

추가적으로 알아두면 도움되는 정보들, 혹은 수정사항들은 댓글로 남겨주세요!

🌈댓글은 언제나 환영입니다🙏🏻

반응형
저작자표시 비영리 변경금지

'Python' 카테고리의 다른 글

[ 프로그래머스 ] 거리두기 확인하기 - python  (0) 2022.02.11
[프로그래머스 level1] 가운데 글자 가져오기 - Python  (0) 2021.07.18
Python 공부 시작!  (0) 2021.07.18

'Python'의 다른글

  • 현재글DFS / BFS 예제 구현해보기 - python

관련글

댓글

티스토리툴바