[Algorithm] DFS & BFS 알고리즘

CS/Algorithm

[Algorithm] DFS & BFS 알고리즘

_PNO 2024. 8. 26. 23:38

DFS & BFS란?

그래프를 탐색하는 2가지의 방식을 의미합니다.

어려운 알고리즘이라고 많이들 착각하시는데, 이해만 잘 하시고 구현에 익숙해지시면 진짜 이것만큼 편한 알고리즘이 없습니다.

서론은 거두절미 하고 본론으로 들어가보도록 합시다.

그래프가 뭔데?

그래프는 자료구조입니다. 저희가 생각하는 막대형 그래프, 꺾은선 그래프같은 모양은 아니고요.
자유분방하게 펼처진 데이터를 선으로 이어준거라 생각하시면 편합니다.

그래프는 데이터들의 "관계" 를 중요시하는 자료구조로써,
각각의 데이터끼리의 관계를 표현한 자료구조입니다.

그래프에 관련된 용어 몇개만 간단히 알아보고 가겠습니다.

노드/정점 (node/vertex)
노드, 정점이라고도 불리는것은 저장된 각각의 데이터를 의미합니다.
위 그림에서는 초록색 원들이 노드입니다.
간선 (edges/links)
간선은 노드를 이어주는 선입니다. 이 선들은 각 데이터간의 관계를 의미합니다.
때문에 그래프가 관계를 중요시하는 자료구조라 볼 수 있는거죠.

그래프 탐색?

자료구조의 정의가 무엇입니까? 자료를 저장하는 방식을 자료구조라고 하죠. 자료를 저장하면,
자료를 사용하는 방법도 당연히 있어야 바람직하겠죠?
그래프에 저장된 데이터를 사용하는 방식이 바로 "그래프 탐색" 입니다.

사실은, 그래프 탐색은 그래프는 자료를 꺼내오는것보단 노드간의 관계를 판단하는 것에 더 중점이 맞춰져 있는데요.
예를들어 "A노드와 B노드는 연결되어 있는가?" 이러한 문제를 해결하기 위해 그래프 전반을 탐색하는것을 그래프 탐색이라 합니다.

Visit 배열

각각의 탐색방법을 알아보기전, visit 배열에 대한 이야기를 해야할 것 같습니다.
탐색을 하다보면, 중복된 노드에 접근하는 일이 생길 수 있습니다.
쉽게 말하면 이미 방문한 노드에 또 접근하는 일이 생길 수 있다는거죠

이게 왜 문제냐 하실 수 있는데, 다음 예제를 볼까요?

해당 예제는 위 그래프에서 1과 5가 연결되어있는지 판단하려고 하는 예제입니다.

1부터 시작했다고 가정하면 1 > 2 > 3 > 4 순으로 탐색을 진행하겠죠?
(1 > 4 > 3 > 2 순으로도 가능합니다)
하지만 아직 5를 만나지 못했으니 탐색을 계속 하려 할때,
이 프로그램은 1번을 방문했는지 기억하지 못합니다.
때문에 1번을 새로운 노드인지 알고 1번을 탐색하고 또다시 2번을 탐색하고를 반복하는겁니다.
결론적으로는 해당 예제는 무한 루프에 빠지게 됩니다.

때문에 저희는 무슨 노드를 방문했었는지 기록을 해야하며,
기록에 사용되는 배열을 visit 배열이라 칭합니다.

visit 배열은 DFS와 BFS를 구현할때 필수적인 개념이며,
visit 배열을 어떻게 구성하냐에 따라 문제의 풀이 방식이 달라지기 때문에 중요한 개념입니다!

DFS(Depth-First Search) 알고리즘

DFS 알고리즘은 깊이 우선 탐색 방법입니다. 말 그대로 깊이를 우선해서 탐색하는겁니다.
각각의 분기에 대하여 완벽하게 탐색하는 방식입니다.

미로에서 한 방향으로 쭉 가다가 막혀있다면 마지막 갈림길로 돌아와 다른 쪽으로 탐색하는 방법과 같습니다.

DFS 구현 (Python3)

graph = [
	[],
    [2, 3], # 1번 노드는 2번, 3번 노드와 연결되어있음
    [1, 4], # 2번 노드는 1번, 4번 노드와 연결되어있음
    [1, 4], # 3번 노드는 1번, 4번 노드와 연결되어있음
    [2, 3],  # 4번 노드는 2번, 3번 노드와 연결되어있음
    [] # 5번 노드는 아무 노드와의 연결이 존재하지 않음
]

def DFS(start, visit = []):
    visit.append(start) 

    for nextNode in graph[start]:
        if nextNode not in visit:
            DFS(nextNode, visit)
    
    return visit

# 4번과 1번이 연결되어있는가?
print("Connected" if 4 in DFS(1) else "Not Connected")

# 5번과 1번이 연결되어있는가?
print("Connected" if 5 in DFS(1) else "Not Connected")

BFS(Breadth-First Search) 알고리즘

BFS 알고리즘은 너비 우선 탐색법이라 불리는 알고리즘입니다. DFS가 분기를 완전탐색했다면,
BFS는 각 분기들을 동시에 탐색하는것을 목표로 합니다.

쉽게 말하면, 현재 기준이 되는 점과 가까운 노드들부터 멀어지는 노드순으로 탐색한다고 생각하시면 편할것 같습니다

BFS 구현 (Python3)

from collections import deque

graph = [
	[],
    [2, 3], # 1번 노드는 2번, 3번 노드와 연결되어있음
    [1, 4], # 2번 노드는 1번, 4번 노드와 연결되어있음
    [1, 4], # 3번 노드는 1번, 4번 노드와 연결되어있음
    [2, 3],  # 4번 노드는 2번, 3번 노드와 연결되어있음
    [] # 5번 노드는 아무 노드와의 연결이 존재하지 않음
]

def BFS(start, visit = []):
    queue = deque([start])
    visit.append(start)

    while queue:
        currunt = queue.popleft()
    
        for nextNode in graph[currunt]:
            if nextNode not in visit:
                visit.append(nextNode)
                queue.append(nextNode)
    
    return visit

# 4번과 1번이 연결되어있는가?
print("Connected" if 4 in BFS(1) else "Not Connected")

# 5번과 1번이 연결되어있는가?
print("Connected" if 5 in BFS(1) else "Not Connected")

두 방식의 차이점 (정리)

구분	DFS	BFS
탐색 방법	각 분기를 완전탐색하는 방법	기준 노드로부터 가까운 노드부터 탐색하기
시간 복잡도 (N은 노드의 개수,E는 간선의 개수)	O(N^2) (비교적 느림)	O(N+E) (비교적 빠름)
구현 방법	재귀함수 또는 스택	양방향 큐 (Deque)
유리한 문제	경로의 특성을 기억해야하는 문제	최단거리를 구하는 문제

티스토리