반응형 BFS11 [알고리즘] DFS (깊이 우선 탐색), BFS(너비 우선 탐색) 포인트 깊이 우선 탐색은 재귀를 주로 사용합니다. 저는 용어를 나누어서 사용해서 헷갈리는 부분이 많았던 것 같습니다. 깊이 우선 탐색과 너비 우선 탐색은 그렇게 다르지 않다. 사실 계속해서 알고리즘 공부를 하면서 생각이 나는 것은 사실 엄청 모르고 있는 것들이 깨어나간다라는 생각이 많이 든다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include using namespace std; vector map; vector visited; int n, m; int u, v; void dfs(int x) { //기본적으로 재귀를 사용한다고 하면 생각하기 쉽다. visited[x] = true; //bfs 처럼 방문 배열 표시를 하고 cout n >> m; map.resize(n.. 2020. 12. 3. [알고리즘] c++ cpp 바이러스 포인트 1. DFS 하고 BFS 를 동시에 이해를 할 수 있는 문제 2. DFS 하고 BFS 는 구조적으로 정형화된 부분이 있어서 반복적으로 어떤 형식으로 흘러가는지를 아는 것은 좋은 것 같다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include #include #include using namespace std; vector map[101]; bool visited[101]; int cnt; void bfs(int a) { queue q; q.push(a); visited[a] = 1; int cnt = 0; while (!q.empty()) { int x = q.front(); q.pop(); for (auto ele : map[x]) { if (!visited[.. 2020. 10. 29. [알고리즘] c++ cpp 지형 이동 포인트 1. bfs, 프림 알고리즘을 섞는다. bfs 는 구역의 이름을 짓기위하여 실행을 한다 프림은 mst 를 구하기 위하여 실행을 한다. 2. 아직 이 문제는 어렵다. 억지로 풀기는 하였다 그래도 중요하다고 생각을 하는 부분은 중간에 있는 calc 함수라고 생각을 한다. calc 를 통해서 맵을 돌면서 인접 섹션이 다른 것들을 노드로 하고 이를 도는 mst 를 만드는 생각이 중요한 것 같다. 프림은 아무리 여러개가 연결이 되어 있어도 결국은 하나의 경로를 택하기 때문에 따로 처리는 상관이 없다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include using namespace std; int section[301][301]; int visited[301][301];.. 2020. 10. 23. [알고리즘] c++ cpp 숨바꼭질 시리즈 (숨박꼭질4) 포인트 1. BFS (너비 우선 탐색) 2. 이번 조건은 방문했던 경로들을 기억을 할 수 있는가 이다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include #include #include using namespace std; const int MAX = 100001; int parent[MAX]; //해당 지점 방문 직전 지점 저장 bool visited[MAX]; vector map; //경로 저장 int n, m; int bfs() { queue q; // 페어 큐를 만든다. q.push({n, 0}); visited[n] = 1; while (!q.empty()) { // 빌때 까지 반복 int x, time; tie(x, time) = q.front(); q... 2020. 10. 4. 이전 1 2 3 다음 반응형