깊이 우선 탐색, 너비 우선 탐색

DFS (깊이 우선 탐색)

• 정의) 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

• 특징)
• 그래프 완전 탐색 기법 중 하나
• DFS 탐색 방식은 후입 선출(LIFO) 특성을 가짐
• 주로 재귀 함수나 스택 자료 구조를 이용해 구현함
• 재귀 사용 시 스택 오버 플로우 유의 필요함
• 시간복잡도 : O(V + E) → 노드 수 : V, 에지 수 : E
• 한 번 방문한 정점은 다시 방문하지 않으며, 한 정점에서 다음으로 방문할 노드들을 순회하는 횟수가 그 정점의 차수와 같기 때문
• DFS 를 응용해 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제를 해결 가능함

• 과정) 스택 이용
1. DFS 를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
• 그래프를 인접 리스트로 표현하기
• 스택 자료구조에 시작 노드 더하기
• 노드 방문 여부 체크할 배열 초기화 → 시작 노드는 방문 여부 true로 체크하기 (T, F, F, F…)
2. 스택에서 노드를 꺼내고, 꺼낸 노드의 인접 노드 중 방문 안 한 노드를 스택에 삽입하기
1. pop 수행해 꺼낸 노드를 탐색 순서에 기입하기
2. 꺼낸 노드의 인접 노드들을 스택에 삽입하기
• 이미 방문한 노드는 방문 배열을 바탕으로 재삽입 하지 않음
3. 스택에 삽입한 노드들의 방문 여부 true로 체크하기
3. 2번을 스택에 값이 없을 때까지 반복하기

• 예시) 스택 이용

• 코드) 스택, 재귀 이용

BFS (너비 우선 탐색)

• 정의) 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 방문하면서 탐색하는 알고리즘

• 특징)
• 그래프 완전 탐색 기법 중 하나
• BFS 탐색 방식은 선입 선출(FIFO) 특성을 가짐
• 주로 큐 자료 구조를 이용해 구현함
• 시간복잡도 : O(V + E) → 노드 수 : V, 에지 수 : E
• 목표 노드에 도달하는 경로가 여러 개일 때 최단 경로를 보장함
• 탐색 시작 노드와 가까운 노드를 우선하여 탐색하기 때문임
• 단순히 방문에서 끝나는 게 아니라, 시작 노드와의 거리를 전부 계산할 수 있음
• 현재 보는 칸으로부터 추가되는 인접한 칸은 현재 보는 칸보다 1만큼 더 떨어져 있기 때문임

• 과정)
1. BFS 를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
• 그래프를 인접 리스트로 표현하기
• 큐 자료구조에 시작 노드 더하기
• 노드 방문 여부 체크할 배열 초기화 → 시작 노드는 방문 여부 true로 체크하기 (T, F, F, F…)
2. 큐에서 노드를 꺼내고, 꺼낸 노드의 인접 노드 중 방문 안 한 노드를 큐에 삽입하기
1. poll 수행해 꺼낸 노드를 탐색 순서에 기입하기
2. 꺼낸 노드의 인접 노드들을 큐에 삽입하기
• 이미 방문한 노드는 방문 배열을 바탕으로 재삽입 하지 않음
3. 큐에 삽입한 노드들의 방문 여부 true로 체크하기
3. 2번을 큐에 값이 없을 때까지 반복하기

• 예시)

• 코드)

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main