BFS

#1. 문제 #2. 풀이 1. BFS 최단 경로 [알고리즘]#2_길 찾기 알고리즘 #1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구 webddevys.tistory.com [정의] : BFS(너비 우선 탐색)은 그래프의 모든 노드를 탐색하는 알고리즘입니다. BFS는 가중치가 없거나 혹은 일정한 경우 그래프의 최단 경로 탐색을 위해 사용할 수 있습니다. [특징] : 큐 활용 2. set 컨테이너 [Basic C++] #29_Set, STL 컨테이너 [Basic C++] #29_Set, STL 컨테이너 C++ 개발에서 STL 컨테이너에 대해 알아보겠습니다. C++가..

#1. 문제 #2. 풀이 1. BFS [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com [정의] : BFS(너비 우선 탐색)은 그래프 내 모든 정점을 탐색하는 방법 중 하나입니다. BFS는 현재 정점과 인접한 정점들을 우선적으로 탐색하며, 큐 자료구조를 활용하여 구현합니다. [특징] : 그래프 내 모든 정점을 탐색하는 것뿐만 아니라, 가중치가 없는 그래프의 "단일-출발 최단 경로" 알고리즘으로 활용됩니다. 2. 단일-출발 최단 경로의 합이 가장 적은 시작 정점 찾기! 먼저, 단일-출발 최단 경로 알고리..

#1. 문제 #2. 풀이 1. 그래프 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 2. DFS [정의] : 깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. [특징] : 깊이 우선 탐색은 한 노드에서 시작해 그래프의 깊은 부분을 우선적으로 탐색하는 방법입니다. [동작 방식] : DFS는 일반적으로 재귀적으로 호출하는 방법과 스택을 활용하는 방법이 있습니다. 재귀적 호출 스택 3. BFS [정의] : BFS(너비 우선 탐색)은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다. ..

#1. 문제 #2. 풀이 1. BFS(너비 우선 탐색) [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com [정의] : BFS(너비 우선 탐색)은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다. [특징] : BFS는 현재 상태에서 가장 인접한 정점들을 우선적으로 탐색하는 방법입니다. [동작 방식] : BFS는 큐를 활용하여 구현 가능합니다. 큐 2. 현재 정점의 방문 순서 기록하기 입력받은 간선 정보를 2차원 벡터에 저장하고, 각 항목에 저장된 vector 컨테이너를 오름차순 정렬합니다. BFS를 수..

#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구성된 그래프에서 최단 경로 혹은 특정 조건을 만족하는(최소 신장 트리, etc) 경로를 찾는 데 사용됩니다. 다양한 종류의 길 찾기 알고리즘이 있으며, 알고리즘의 선택은 그래프의 크기, 가중치의 종류, 실행 시간 제약 등을 고려합니다. 따라서, 알고리즘의 특징과 제약 사항 등을 이해해야 주어진 문제에 가장 적합한 알고리즘을 선택할 수 있습니다.[종류]1. "단일 출발(single-source)" :  주어진 단일 노드 v로부터 다른 모든 노드 사이의 최단 경로를 찾는 문제 2. "단일 쌍(single-pair)" :..