기록

백준 알고리즘을 푸는 도중 알게된 지식을 기재하였습니다. https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS 문제를 접하게 되면, 흔하게 나오는 단어들이 있습니다. 노드 (Node) / 정점(vertex) → 그래프에서의 특정 위치나 개체를 나타내는 단위입니다. 간선 (Edge) → 그래프에서 노드 간의 관계를 나타내는 선입니다. → 정점을 연결하며, 방향성과 가중치 등의 속성을 가질 수 있습니..

DFS (Depth First Search) DFS는 깊이 우선 탐색 알고리즘으로, 특정한 경로를 따라 최대한 깊숙히 들어가면서 노드를 탐색하는 알고리즘입니다. 스택 자료구조 또는 재귀 함수를 통해 구현할 수 있습니다. DFS 알고리즘은 시작 노드에서부터 한 방향으로 갈 수 있는 경로를 모두 탐색하고, 갈 수 있는 경로가 더 이상 없다면 다시 바로 이전 노드로 돌아와 다른 방향으로 다시 탐색합니다. 이러한 과정을 모든 노드를 방문할 때까지 반복합니다. DFS 알고리즘의 시간 복잡도는 최악의 경우 모든 노드를 방문해야 하므로 O(V + E) 입니다. BFS (Breadth First Search) BFS는 너비 우선 탐색 알고리즘으로, 특정한 경로를 따라 이동할 때 너비를 우선으로 탐색하는 알고리즘입니다...