[SW 정글 19일차] DFS와 BFS

이번 주차는 DFS, BFS, 위상정렬에 대해 공부하는 주차로 그냥 단순히 DFS가 무엇인지, BFS가 무엇인지 알고만 알고리즘 문제를 풀어와서 이번 기회에 이렇게 글로 정리하며 개념을 다잡으려고 한다.

 

 

 

1. DFS (Depth-First Search)

DFS는 그래프 탐색 알고리즘 중 하나로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로 시작점부터 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법이다.

DFS는 스택 자료구조나 재귀함수를 이용하여 구현할 수 있고 노드를 탐색 전에 방문 여부를 검사해야한다.

DFS의 시간 복잡도는 인접 리스트로 표현된 그래프에서는 O(N+E)이고 인접 행렬로 표현된 그래프에서는 O(N^2)이다.

그래프 탐색이란?
그래프에서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

DFS가 어떻게 그래프를 탐색하는지 이해하기 쉽게 해주는 시각화 자료가 있어 가져와 봤다.

출처: https://coding-factory.tistory.com/611

DFS의 동작 과정은 아래와 같다.

(재귀함수가 아닌 스택 자료구조를 사용한다는 가정 하게 과정을 설명)

1. 탐색 시작 노드를 스택에 삽입하고 해당 노드를 방문 처리 해준다.
2. 스택의 최상단 노드의 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 만약에 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복한다.

 

이러한 DFS 알고리즘의 장점과 단점은 무엇일까?

- DFS 장점

① 현재 경로상의 노드들만 저장하고 있으면 되어 저장 공간을 비교적 적게 차지

② 탐색하고자하는 목표 노드가 깊은 레벨에 있는 경우에 탐색을 빨리 완료할 수 있음

③ 구현이 BFS보다 간단함

 

- DFS 단점

① 단순 탐색 속도는 BFS에 비해 느림

② 찾고자하는 값이 없을 경우에 너무 깊이 빠질 가능성이 있음

③ DFS는 찾고자하는 값을 구하면 탐색이 종료되어 최단 경로가 된다는 보장이 없음

 

 

이제 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)

 

DFS 알고리즘을 구현하는 코드 자체는 심플해보이지만 문제에 적용하려면 너무 어려운 것같다.

 

 

 

 

1. BFS (Breadth-First Search)

BFS는 그래프 탐색 알고리즘 중 하나로 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘으로 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문함으로써 노드를 넓게 탐색한다.

주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 BFS를 사용한다.

BFS는 큐 자료구조를 이용하여 구현할 수 있고 노드를 탐색 전에 방문 여부를 검사해야한다.

BFS의 시간 복잡도는 인접 리스트로 표현된 그래프에서는 O(N+E)이고 인접 행렬로 표현된 그래프에서는 O(N^2)이다.

 

 

아래의 시각화 자료를 보며 BFS가 어떻게 탐색이 이루어지는지 이해해보자.

출처: https://coding-factory.tistory.com/612?category=794828

BFS의 동작 과정은 아래와 같다.

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

 

이러한 BFS 알고리즘의 장점과 단점은 무엇일까?

- BFS 장점

① 노드의 수가 적고 깊이가 얕은 경우에 빠르게 동작

② 단순 탐색 속도가 DFS보다 빠름

③ 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장

 

- BFS 단점

① 큐에 다음에 탐색할 정점들을 저장해야하므로 저장공간이 비교적 많이 필요

 

 

마지막으로 BFS알고리즘을 코드로 구현하면 아래와 같다.

from collections import deque

def dfs(graph, start, visited):
    queue = deque([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

큐를 구현할 때 deque를 쓰는 것이 기본적으로 제공하는 리스트를 사용하는 것보다 pop할 때 시간복잡도 면에서 효율적이다.

 

 

 

마지막으로 그래프에 대한 설명이 잘 되어 있는 글이 있어 공유하려고 한다.

시간이 되면 따로 정리를 해봐야겠다.

https://coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

---

[오늘의 나는 어땠을까?]

오늘은 정글에 들어오고나서 정말 그냥 무난한 하루였던 것같다.

특별히 나에게 새로운 느낌을 받게하는 에피소드도 없고 어떠한 생각의 변화도 없었다.

그냥 아침에 와서 어제 고민하던 문제를 풀고 점심을 먹고도 문제를 풀고 저녁을 먹고도 문제를 풀면서 보냈다.

 

생각해보니 뭔가 이전 주차들보다는 문제가 안풀려도 재미는 있는 것같다.

알고리즘에 대해 친숙해서인지는 모르겠지만 그냥 그래프 탐색이라는 주제가 재밌는 것 같다.

물론, 맞왜틀(맞았는데 왜 틀려)를 외치며 한숨이 절로 나올때도 있지만 그래도 다른 알고리즘에 비해 이해가 더 잘된다.

 

이러한 흥미가 단순히 흥미로 끝나는 것이 아니라 그래프 탐색 문제를 마주했을 때는 완벽히 풀 수 있게 되고 싶다.

그럴려면 더 시간을 투자해서 노력을 하자

 

---

<참고 자료>

https://coding-factory.tistory.com/611

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://www.youtube.com/watch?v=7C9RgOcvkvo&t=2179s 

https://blog.naver.com/ndb796/221230944971

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://coding-factory.tistory.com/612?category=794828