Algorithms for Reversing

• List :

boj

solved.ac

BFS/DFS

**BFS(**너비 우선 탐색)

• 시작 정점에서 가까운 정점들을 먼저 방문하는 방식.
• 주로 큐(Queue) 자료구조를 사용.
• 최단 경로(가중치가 동일한 경우)를 구할 때 자주 사용됨.
• 탐색 순서 예시:
  1. 시작 정점 방문 후 큐에 삽입
  2. 큐에서 원소를 꺼냄(pop)
  3. 해당 원소와 인접한(연결된) 아직 방문하지 않은 정점을 모두 방문 처리 후 큐에 삽입
  4. 큐가 빌 때까지 2~3번 과정을 반복

**DFS(**깊이 우선 탐색)

• 시작 정점에서 출발하여 한 방향으로 갈 수 있을 때까지 쭉 진행(깊이 우선) 후, 막히면 다시 돌아와 다른 경로를 탐색.
• 주로 스택(Stack) 또는 재귀 함수로 구현.
• 경로의 존재 여부, 사이클(순환) 유무 등을 판별할 때 자주 사용됨.
• 탐색 순서 예시(재귀 기반 가정):
  1. 시작 정점을 방문
  2. 해당 정점과 인접한(연결된) 아직 방문하지 않은 정점을 재귀 호출로 탐색
  3. 더 이상 방문할 인접 정점이 없으면 재귀 함수를 종료하면서 되돌아감

Tree

Implementation

DP(Dynamic Programming)