728x90 dfs2 [백준 24479] 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/problem/24479 문제 분석 입력 받아 그래프를 만들고 DFS로 탐색을 하고, 탐색 순서를 기록하여 출력하는 형식에 문제이다. 이 문제는 DFS만 알고 있다면 딱히 문제 없이 풀 수 있을 것이라고 생각된다. 코드 #include #include #include using namespace std; vector graph; vector visited; int result[100001]; int cnt = 0; void DFS(int index); int main() { int n, m, r, input1, input2; cin >> n >> m >> r; graph.resize(n + 1); visited.resize(n + 1, false); while .. 2023. 8. 1. [알고리즘 이론] DFS와 BFS 더보기* DFS와 BFS 이해 전 그래프에 대한 이론을 알고 있다면 도움이 될 것이다. DFS 깊이 우선 탐색(Depth-First Seartch)는 그래프 완전 탐색 기법 중 하나이다. DFS는 그래프의 시작 노드부터 시작하여 탐색할 분기를 정하고, 끝까지 탐색 후 다음 분기로 넘어가서 다시 탐색하여 모두 다 탐색하는 알고리즘이다. DFS는 Stack 또는 재귀함수를 이용하여 구현할 수 있으며 시간 복잡도는 O(노드 수 + 에지 수)이다. 재귀함수를 사용할떈 스택 오버플로를 조심하며 사용해야한다. 우선 이런 그래프가 있다고 가정해보자. 이 그래프를 인접 리스트로 표현한다면 아래처럼 표현 할 수 있다. 1) 1부터 시작한다고 가정하고 1을 Stack에 넣음과 동시에 1이 들어 왔다는 것을 체.. 2023. 8. 1. 이전 1 다음 728x90
