- 스택 (stack)
https://www.youtube.com/watch?v=WB_BoAgWLNU&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=14
https://blog.naver.com/ndb796/221230937978
13. 스택(Stack)
스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 가장 기본이 되는 자료구조입니다. 말 그대로 자료를...
blog.naver.com
- 깊이 우선 탐색 (DFS)
https://www.youtube.com/watch?v=l0Rsu7dziws&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=17
https://blog.naver.com/ndb796/221230945092
16. 깊이 우선 탐색(DFS)
깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐...
blog.naver.com
- 예제 코드
#include <iostream>
#include <vector>
using namespace std;
int number = 7; // 그래프의 노드 수
int c[8]; // 방문 여부를 저장하는 배열
vector<int> a[8]; // 인접 리스트로 그래프를 표현하는 배열
void dfs(int x) {
if (c[x]) return; // 노드를 이미 방문한 경우, 함수를 종료하고 돌아갑니다.
c[x] = true; // 노드를 처음 방문한 경우, 방문 여부를 true로 표시합니다.
cout << x << ' '; // 현재 노드를 출력합니다.
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
dfs(y); // 현재 노드와 연결된 모든 인접 노드에 대해 재귀적으로 dfs 함수를 호출합니다.
}
}
int main(void) {
// 그래프의 간선을 설정합니다.
// 1과 2를 연결합니다.
a[1].push_back(2);
a[2].push_back(1);
// 1과 3를 연결합니다.
a[1].push_back(3);
a[3].push_back(1);
// 2과 3를 연결합니다.
a[2].push_back(3);
a[3].push_back(2);
// 2과 4를 연결합니다.
a[2].push_back(4);
a[4].push_back(2);
// 2과 5를 연결합니다.
a[2].push_back(5);
a[5].push_back(2);
// 3와 6를 연결합니다.
a[3].push_back(6);
a[6].push_back(3);
// 3와 7을 연결합니다.
a[3].push_back(7);
a[7].push_back(3);
// 4와 5를 연결합니다.
a[4].push_back(5);
a[5].push_back(4);
// 6과 7을 연결합니다.
a[6].push_back(7);
a[7].push_back(6);
// DFS를 수행합니다.
dfs(1); // DFS를 시작 노드 1에서 시작합니다.
return 0;
}
'자료구조와 알고리즘 > [인강] 자료구조와 알고리즘' 카테고리의 다른 글
큐 (queue) & 너비 우선 탐색 (BFS) (0) | 2023.10.22 |
---|