[C++] 벡터 사용법 / 깊이우선탐색 DFS

- C++의 벡터는 동적 배열구조 클래스

- 자동으로 배열의 크기 조절과 추가 삭제 가능

- 모든 자료형에 대해 배열처럼 저장 가능 But 한번에 한 타입만 저장 가능

- 자바 벡터처럼 배열 크기 추가할 때, 기존 배열 크기의 100% 늘어남

vector<int> integer_vector;
vector<double> double_vector;
vector<char> char_vector;

 

 

- 벡터의 기본 함수

//iterator 반복자
begin()		 //beginning iterator 반환
end() 		//end iterato 반환

//추가 및 삭제
push_back(element) 		//벡터 제일 끝에 원소 추가
pop_back()		 //벡터 제일 끝 원소 삭제

//조회
[i] 		//i번째 원소 반환
at(i)		 //i번째 원소 반환
front()		 //첫번째 원소 반환
back()		 //마지막 원소 반환

//etc
empty()		 //벡터가 비어있으면 true 아니면 false 반환
size() 		//벡터 원소들의 수 반환

 

- 벡터와 배열의 차이 : 벡터는 동적으로 원소 추가 가능하며 크기가 자동으로 늘어남

 

- 깊이 우선 탐색(Depth First Search)에서의 벡터사용

#include <iostream>
#include <vector>

using namespace std;

int number = 9; //노드 수
int visit[9]; //방문한 노드
vector<int> a[10];

void dfs(int start) {

	if (visit[start]) {
		return; //방문한 경우 바로 빠져나옴
	}

	visit[start] = true; //방문했으니깐 1 넣기
	cout << start << " "; // 출력

	for (int i = 0; i < a[start].size(); i++) {
		//인접 노드 방문
		int x = a[start][i];
		dfs(x);
	}
}

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와 4연결
	a[2].push_back(4);
	a[4].push_back(2);

	//4와 8연결
	a[4].push_back(8);
	a[8].push_back(4);

	//2와 5연결
	a[2].push_back(5);
	a[5].push_back(2);

	//5와 9연결
	a[5].push_back(9);
	a[9].push_back(5);

	//3과 6연결
	a[3].push_back(6);
	a[6].push_back(3);

	//3과 7연결
	a[3].push_back(7);
	a[7].push_back(3);

	dfs(1); //1에서 시작

	return 0;

}