[DFS, BFS 01]

 

https://www.acmicpc.net/problem/1260

#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
vector<int> v[1001];
bool visit[1001];
void bfs(int startIndex) {
	queue<int> q;
	q.push(startIndex);
	visit[startIndex] = true;

	while (!q.empty()) {
		// 큐에 값이 있을 경우 계속 반복
		// 큐에 값이 있다 -> 아직 방문하지 않은 노드가 존재함

		int x = q.front();
		q.pop();
		printf("%d ", x);

		// x index 의 vec size(개수)만큼 훑음
		for (size_t i = 0; i < v[x].size(); i++) {	

			// x index 의 vec , i번째 노드의 값을 가져옴
			int y = v[x][i];
			
			if (!visit[y]) {	// y번의 visit 이력을 체크해서
				// 방문하지 않았다면
				q.push(y);	// 큐에 y를 추가함.
				visit[y] = true;	// 노드 y 방문 이력 남김
			}
		}
	}
}

void dfs(int startIndex) {
	stack<int> s;
	s.push(startIndex);		// stack 에 push start node number 
	visit[startIndex] = true;	// bfs 처럼 startIndex 위치 visit 이력 남기고
	
	printf("%d ", startIndex);	// 방문했으니까 print

	while (!s.empty()) {	// stack 이 완전히 비어버릴(탐새 될)때까지 반복
		int currentNode = s.top();	// 스택의 top을 현재 보고있는 노드로 가져옴
		s.pop();	// 가져온뒤 볼일없으니 pop

		// 현재 노드의 vec size(개수)만큼 훑는데, visit 안한 다음노드 찾으면 break 할예정
		for (size_t i = 0; i < v[currentNode].size(); i++) {
			int nextNode = v[currentNode][i];	// currentNode 의 i 번째 직속자식

			if (visit[nextNode] == false) {	// nextNode 의 방문 이력이 없다면
				printf("%d ", nextNode);	// nextNode 출력한뒤
				visit[nextNode] = true;	// nextNode 방문이력 남김
				
				s.push(currentNode);
				s.push(nextNode);
				break;
			}
		}
	}
}

int main()
{
	int N,M,V;

	scanf_s("%d %d %d", &N, &M, &V);
	
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf_s("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}

	for (int i = 1; i <= N; i++) {
		sort(v[i].begin(), v[i].end());
	}

	fill(visit, visit + N+1, false);
	dfs(V);
	printf("\n");
	fill(visit, visit + N+1, false);
	bfs(V);



	return 0;
}

 

 

DFS, BFS

DFS 는 스택, 재귀함수

BFS 는 큐로 만들 수 있다.

 

스택이나 재귀나 구조가 똑같아서,

서로 완전히 호환된다고 보면 됨.

 

그런데 재귀로 하는게 훨씬 더 편하다 :D 

 

---

@ 변수를 통해서 배열을 동적으로 생성

vector<int> graph[size];
// Visual Studio의 경우
/* 변수를 통해서 배열을 동적으로 생성할 때
vector<int> * graph = new vector<int>[n+1];
*/

→ 굉장히 유용하게 쓸듯

 

 

@ 배열 (이번 경우는 vector) 의 start 부터 end 까지 value 로 채워줌

fill(start, end, value);

→ 세상 편하다..

 

 

 

---

 

둘 모두 동작방식은 알았는데, 이렇게 직접 큐와 스택을 구현해보니 신기하기도하고 재미있었음.

 

이번주말까지 

 

경로 찾기

연구소

로또

거의 최단 경로

 

요친구들 정복할 예정.

그러고나서 히구랑 다음진도 나가자