그래프 탐색 방법
1. 깊이 우선 탐색[DFS (Depth-First Search)]
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다른 분기(branch)로 넘어가기 전에
해당 분기를 완벽하게 탐색하는 방식이다.
스택(선입후출), 재귀함수로 구현한다.
sojeong-lululala.tistory.com/5
[BOJ] [Python] 2775번 : 부녀회장이 될테야
간단한 예시를 만들어 작성하면서, 어떻게 문제를 풀어야 할 지 생각했다. 그렇게 떠올린 방법은 '재귀함수 사용' loop = int(input()) #test def people(a, b): global result if(a == 0): return b else: for i..
sojeong-lululala.tistory.com
2. 너비 우선 탐색[BFS (Breadth-First Search)]
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방식이다.
큐(선입선출)로 구현한다.
DFS와 BFS 기본 문제
sojeong-lululala.tistory.com/7
[BOJ] [Python] 1260번 : DFS와 BFS
sojeong-lululala.tistory.com/6 BFS DFS 공부를 하면서 풀어봤다. DFS는 재귀함수, BFS는 deque를 이용했다. from collections import deque # 입력 num = list(map(int , input().split())) n = num[0] #정점 개..
sojeong-lululala.tistory.com
*그래프: 정점과 간선으로 이루어진 자료구조의 일종
*그래프 탐색: 하나의 정점을 시작으로 모든 정점을 한 번씩 방문하는 것
'알고리즘 > 개념' 카테고리의 다른 글
| [정렬] 병합 정렬 [Merge Sort] (0) | 2021.12.01 |
|---|---|
| [최소 신장 트리] 프림[Prim] 알고리즘 (0) | 2021.10.08 |
| [정렬] 위상 정렬(Topological Sort) (0) | 2021.10.02 |
| [최단 경로 트리] 다익스트라 알고리즘[Dijkstra] (0) | 2021.05.18 |
| [이진 탐색] 이진 탐색[Binary Search] (0) | 2021.05.06 |
