[c++] vector로 DFS 구현하기

오늘은 c++의 STL(Standard Templete Liberary) 중 하나인 vector를 공부하고 이걸로 DFS를 구현해서 계속해서 알고리즘 문제를 풀 때 응용을 하려고 한다 알고리즘 문제를 풀다보면 더 반복되는 부분이 많이 나올텐데 계속 구현하며 더 효율적으로 짤..수도 있겠지만 하나의 틀을 만들어서 응용해서 계속 사용하려고 한다

일단 벡터는 거의 c의 배열이랑 비슷한거 같긴하다 하지만 배열에서 확장된 기능을 가지고 있다

나는 완전히 벡터 공부를 정복할려는게 아니니까 간단히 내가 사용할? 부분만 찾아서 정리해야겠따

vector에 가장 큰 특징 중 하나는 원소가 하나의 메모리 블록에 연속하게 저장된다는 것이라는데(무조건 데이터를 선형적으로 만들려고) 그래서 원소가 추가되거나 삽입될 때 메모리를 재할당하게 돼서 속도가 느려지는 경우가 있다고 한다

-> 저장 공간보다 많은 양의 데이터를 추가 시킬 경우에 현재 보유한 메모리의 두배만큼을 할당하기때문에 단순하게 +1 을 위한 추가 할당으로는 비효율적일거같다 알고리즘을 풀다보니까 문제 해결에 필요한 시간을 줄이는 것도 중요하기때문에 이런 부분은 기억해두면될거같다

•  <vector> 헤더파일을 추가해야한다

•  using namespace std;를 해주면 편리하다

• vector<[data type]> [변수이름] 으로 선언한다 ex) vector<int> a;

1. vector의 생성자와 연산자

• vector<[data type]> a;  : 비어있는 vector a를 만든다

• vector<[data type]> a(10);  : 기본값으로 초기화 된 10개의 원소를 가지는 vector a를 만든다

• vector<[data type]> a(10, 초기화값);  : 지정한 초기값으로 된 10개의 원소를 가지는 vector a를 만든다

• vector<[data type]> b(a); : vector b는 vector a를 복사해서 만든다

• vector들이 있을 때 내부의 인자들끼리 연산은 '==', '!=', '<', '>', '<=', '>=' 로 비교할 수 있다

2. vector 함수

vector<int> v; 를 만들었다고 생각하고 함수를 사용해보겠다!

• v.assign(10, 1) : 1이라는 값으로 10개의 원소에 할당

• v.at(i) : i번째 원소를 return한다 vector의 범위를 체크하므로 []로 참조하는 것보다 느림

• v[i] : i번째 원소를 return한다 범위를 체크하지않으므로 at보다 빠름

• v.front() : 첫번째 원소를 return 한다

• v.back() : 마지막 원소를 return 한다

• v.clear() : 모든 원소를 제거한다(메모리공간은 남아있다) -> 빈컨테이너로 만든다

• v.push_back(5) : 마지막 원소 뒤에 5를 삽입한다

• v.pop_back() : 마지막 원소를 제거

• v.begin() : 첫번째 원소를 가리키는 반복자를 return

• v.end() : 마지막 원소를 가리키는 반복자를 return 

• v.rbegin(), b.rend() : reverse begin, reverse end

• v.reserve(n) : n개의 원소를 저장할 공간을 예약(미리 동적할당)

• v.resize(n) : vector의 크기를 n으로 변경, 더 커질경우 0으로 초기화

• v.resize(n, 1) : vector의 크기를 n으로 변경하고 더 커질경우 1로 초기화

• v.size() : vector 원소의 개수를 return

• v.capacity() : 할당된 공간의 크기를 return

• v2.swap(v1) : v1과 v2의 원소와 capacity를 바꿔줌

• v.insert(3, 4) : 3번위치에 값 4를 삽입, 삽입한 곳의 반복자 return

• v.insert(3, 4, 5) : 3번 위치에 4개의 값 5를 삽입

• v.erase(반복자) : 반복자가 가리키는 원소를 제거

• v.empty() : vector가 비어있는지를 본다 비어있으면 true

3. DFS 구현

DFS는 Depth First Search의 약자로 깊이 우선 탐색 방식이다 그래프에서 한 vertex에서 시작해서 갈 수 있는 vertex로  계속해서 방문을 해나가다가 막히면 돌아가서 다른 vertex로 가는 방법이다 그래프로 보면 한번에 이해할 수 있다

방문을 할 때 그 vertex를 vector에 저장해두고 막힐때 마지막 원소값을 받아오고 pop_back()을 해서 계속해서 탐색을 이어나가면 될거같다

vector를 응용하고 싶은데 그래프를..어떻게 만들지 고민된다

따로 stack을 만들 필요가 없었다...그냥 방문했는지 확인한다음에 방문안했다면 스택에 넣지않고 바로 그아이에서 DFS를 이어나가게 하면된다

• 코드

#include<stdio.h>

#include<iostream>

#include<vector>

using namespace std;

class Graph{

public:

vector<vector<int>> adj;

vector<bool> visited;

int N;//vertex의 개수

Graph(){}

Graph(int n)

{

N = n;

adj.resize(n);

visited.resize(n);

}

void makeEdge(int u, int v)

{

adj[u].push_back(v);

adj[v].push_back(u);

}

void DFS(int i)

{

vector<int>::const_iterator next;

visited[i] = true;

printf("%d\n",i);

for(next = adj[i].begin() ; next != adj[i].end() ; next++) 

{

if(visited[*next] != true){

DFS(*next);

}

}

}

};

void main()

{

int i, e, u, v, n;

scanf("%d", &n);

Graph G(n);

scanf("%d", &e);

for(i=0;i<e ;i++){

scanf("%d %d", &u, &v);

G.makeEdge(u, v);

}

G.DFS(0);

}