기록보관소

DFS와 BFS는 DFS와 BFS에 대한 가장 기초적이면서도 중요한 문제입니다. DFS와 BFS에 대한 충실한 이해가 필요합니다. DFS의 경우 처음 발견된 노드를 기준으로 그 노드에 연결된 노드들을 탐색(DFS)를 하는 알고리즘입니다. 여기서 눈치챌 수 있듯이 DFS는 재귀함수로 구현할 수 있습니다. BFS는 너비우선탐색이라는 이름에서 알 수 있듯이 루트 노드를 기준으로 방사형으로 탐색하는 알고리즘입니다. 즉, 루트 노드에서 거리가 1인 노드들을 전부 탐색한 다음 거리가 2인 노드를 탐색하는 방식으로 탐색이 진행됩니다. 이러한 방식으로 탐색하기 위해 BFS는 '큐'라는 자료구조를 활용하여 구현할 수 있습니다. 큐, DFS, BFS에 대한 설명은 다음과 같습니다. 2021.07.07 - [알고리즘/이론]..

그래프를 깊이 검색하는 알고리즘이다. 최근에 발견되었으나 아직 조사되지 않은 간선을 가진 정점에서 나오는 간선을 조사하고, 그 간선들의 조사가 끝나면 그 정점이 유래한 정점으로 되돌아가 해당 정점에서 나오는 간선을 조사한다. 출발점으로부터 도달가능한 모든 정점을 발견할 때까지 검색이 계속되며, 발견되지 않은 정점이 있다면 다른 출발점을 선택하고 검색을 반복한다. 너비 우선 검색과 달리 출발점이 여러 개가 있는 것으로 생각하지만 이는 알고리즘의 응용할 때 필요가 반영된 결과이다. 검색을 하면서 새로운 원소를 발견하면 그 원소에는 직전원소를 기록하며, 이를 통해 직전원소 부분 그래프를 형성할 수 있다. 너비 우선 검색과 달리 출발점이 여러 개가 될 수 있기 때문에 깊이 우선 트리의 개수 또한 여러 개가 될 ..