🎨 배경

다른 이유는 없고 너무 많이 나오는 개념이다.
계속해서 인터넷에서 찾아보기엔 시간이 너어무 아까워서 여기에 적어놓으려고 한다.
결국 내가 보기위해 적는 것이다.

💡 개념

DFS, BFS 둘 다 그래프 탐색에 사용할 수 있지만, 탐색 방식과 장단점이 다르다.
문제에 따라 적절한 알고리즘을 선택해야 한다.

DFS (깊이 우선 탐색 알고리즘)

현재 노드에서 출발하여 연결된 노드를 차례대로 탐색하며, 더 이상 탐색할 노드가 없을 때까지 재귀적으로 호출한다.

• 스택 자료구조를 사용한다. (LIFO)
• 루트노드에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식을 말한다.
• 위의 그림처럼 DFS는 깊이우선적으로 탐색을 진행하고, 재귀적으로 아래에서부터 탐색하지 않은 정점이 있는지 확인하는 방법이다.

😀 장점:

• 메모리 소모가 대체적으로 작다.
• 방문한 노드들을 스택(Stack)에 저장하기 때문에 BFS보다 메모리 사용량이 상대적으로 작다.
• Backtracking이 가능하며, 미로 찾기와 같은 문제에서 효율적이다.

🙁 단점:

• 최소 거리를 보장하지 않습니다.
• 시작 노드로부터의 최단 경로를 찾는 경우에는 BFS를 사용하는 것이 더 효율적입니다.
• 그래프가 순환 구조일 경우, 무한 루프에 빠질 수 있습니다. 따라서 방문한 노드를 표시하는 방법을 사용하여 이를 방지해야 합니다.

visited = [False] * (n+1) # 예시

• 가끔 재귀 호출의 깊이 제한 sys.setrecursionlimit()을 설정해야 한다.

import sys
sys.setrecursionlimit(10**6) # 예시

• 일반적으로 재귀 호출의 깊이는 1000~3000이다.

• 단, 너무 큰 값을 설정하면 시스템의 스택 오버플로를 방지하지 못할 수 있고, 이는 프로그램의 비정상 종료로 이어질 수 있다.

• 기본적인 코드 구조

'''
def DFS(x,y):
	if 재귀를 종료시킬수 있는 조건문:
    	return
    변수 업데이트
    if visited == False and graph나 다른 조건에 위배되지 않는다면:
    	visited[] = True
        DFS(new_x, new_y)
'''

BFS (너비 우선 탐색 알고리즘)

현재 노드에서 출발하여 연결된 모든 노드를 큐에 삽입하고, 큐가 비어질 때까지 큐에서 노드를 꺼내 탐색한다.
작동방식

• 큐 자료구조를 사용한다. (LIFO)

😀 장점:

• 최소 거리를 보장합니다.
• 시작 노드로부터의 최단 경로를 찾을 때 사용하기 적합합니다.
• 그래프가 순환 구조일 경우, 무한 루프에 빠지지 않습니다.

🙁 단점:

• 메모리 소모가 대체적으로 큽니다.
• 방문한 노드들을 큐(Queue)에 저장해야 하므로 탐색 과정에서 메모리 사용량이 증가합니다.

from collections import deque
queue = deque() # 예시

• 탐색 속도가 DFS에 비해 느릴 수 있습니다.
• 기본적인 코드 구조

'''
def BFS(x,y):
	queue.append((x,y))
    while queue:
    	a,b = queue.popleft()
        if vistied == False and new_a, new_b가 조건에 위배되지 않는다면 
        	queue.append((nx,ny))
'''