Algorithms for Reversing
boj
solved.ac
BFS/DFS
**BFS(**너비 우선 탐색)
- 시작 정점에서 가까운 정점들을 먼저 방문하는 방식.
- 주로 큐(Queue) 자료구조를 사용.
- 최단 경로(가중치가 동일한 경우)를 구할 때 자주 사용됨.
- 탐색 순서 예시:
- 시작 정점 방문 후 큐에 삽입
- 큐에서 원소를 꺼냄(pop)
- 해당 원소와 인접한(연결된) 아직 방문하지 않은 정점을 모두 방문 처리 후 큐에 삽입
- 큐가 빌 때까지 2~3번 과정을 반복
**DFS(**깊이 우선 탐색)
- 시작 정점에서 출발하여 한 방향으로 갈 수 있을 때까지 쭉 진행(깊이 우선) 후, 막히면 다시 돌아와 다른 경로를 탐색.
- 주로 스택(Stack) 또는 재귀 함수로 구현.
- 경로의 존재 여부, 사이클(순환) 유무 등을 판별할 때 자주 사용됨.
- 탐색 순서 예시(재귀 기반 가정):
- 시작 정점을 방문
- 해당 정점과 인접한(연결된) 아직 방문하지 않은 정점을 재귀 호출로 탐색
- 더 이상 방문할 인접 정점이 없으면 재귀 함수를 종료하면서 되돌아감
Tree
Implementation
DP(Dynamic Programming)