[ALPS Study] 탐색 -그래프와 DFS(깊이 우선 탐색)(2)

*C++에 있는 유용한 STL

#include <vector>
// vector : T type data를 contain하는, 크기가 정해지지 않은 배열

vector< T > name; //이와 같은 방식으로 선언
name.begin() //시작 iterator(주소 개념) 반환
name.end() //끝 iterator(끝 주소+1) 반환
name.size() // name에 들어있는 원소의 수 반환
name.resize(int a, T b) //name의 크기를 a로 조정, 빈 칸은 b로 초기화(b 생략 가능, 0으로 초기화)
name.empty() //name이 비었다면 true, 원소가 있다면 false 반환
name[i] //name의 i번째 원소에 접근
name.front() // name의 첫번째 원소에 접근
name.back() // name의 마지막 원소에 접근
name.push_back(T a) //name 가장 뒤에 a 추가
name.pop_back() // name 가장 뒤 원소 삭제(메모리까지 같이 삭제)

---

 iterator 란? 

" An iterator is an object that can iterate(navigate) over elements "

이터레이터는 컨테이너의 원소들을 순회할 수 있는 객체이다.

혹은 일종의 포인터로서, 컨터에너의 특정의 위치를 가르킨다.

[출처] [STL] Iterator (반복자) 정리 및 Iterator 패턴 구현|작성자 호로요이이

 

---

#include <algorithm>
 // sort : 원하는 구간을 Comp에 따라 정렬
 sort(RandomAccessIter first, RandomAccessIter Last, Compare comp) //꼴로 사용할 수 있음
 //[first, last) 구간에 적용
 //comp를 작성한 경우 작성한 comp에 따라 정렬하고, comp를 생략한 경우 Opertor < 에 따라 정렬(오름차순)
 
 //i.e. 내림차순 정렬을 하는 comp 함수
 bool comp(int a, int b){
 	return a>b;
}

스터디 듣고 열심히 이해해보려 했지만 아직 잘 모르겠다. c++은 안 써봐서..! 차차 이해하게 되겠지

 

인접 행렬과 인접 리스트 구현

: MAX개의 NODE가 있고 간선의 정보가 M쌍의 S,E로 주어짐(S와 E가 연결됨), 그래프의 방향성 X

 

-인접 행렬의 구현  

int adj[MAX][MAX] = {};//간선의 개수 정보를 저장할 배열
int S, E;
for (int i = 0; i < M; i++) {
	scanf("%d %d", &S, &E);
	adj[S][E] += 1; //S와 E가 연결되었으면 배열을 1 증가
 	if (S != E) adj[E][S] += 1; //방향이 없는 그래프이므로 S랑 E가 같지 않으면(자기 자신으로 돌아오는 루프가 아니면) 반대 경우도 1증가
	}
}      

-인접 리스트의 구현

vector<int> adj[MAX]; //확장가능한 vector들의 배열을 만듦
int S, E;
for(i=0; i<M; i++){
	scanf("%d %d",&S,&E);//C++이어야 하는데 C++문법을 모르므로 C언어대로 간다.
    adj[S].push.back(E); //S와 E가 연결되어 있으면 adj[S]에 E를 추가
    if(S != E) adj[E].push_back(S); //루프일 때 제외하고 반대로도 연결
}
for(i=0;i<M;i++) sort(adj[i].begin(), adj[i].end()); // 오름차순으로 정렬

* 이 때 vector<int> adj[MAX] 대신 vector<vector<int> > adj로 선언해도 됨.

(이차원 배열과 유사한 이차원 벡터 정도로 생각하면 될 듯)

 

*위 경우는 C++일 때! python일 경우 python 자체 내에 있는 리스트 기능을 이용, C언어는 당연히! 링크드리스트를 이용해야만 함.

*C++에 있는 유용한 STL(2)

#include<stack>
//stack : T type data를 contain하는 후입선출(LIFO)형 자료구조

stack< T > name; //선언
name.size() // name에 들어있는 원소의 수 반환
name.empty() // name이 비었다면 true, 원소가 존재하면 false
name.top() // name의 가장 마지막 원소에 접근
name.push(T a) // name의 가장 뒤에 a 추가
name.pop() // name의 가장 뒤 원소 삭제

 

DFS 구현

: NODE는 총 MAX개(0~MAX~1번), 간선의 정보는 adj라는 vector에 adj list로 저장됨

 

①  Recursive 방식

#include<stdio.h>
visit[MAX]; //방문 여부를 저장할 배열
void dfs(int cur){
	if(visit[cur]) return; //이미 방문한 노드라면 return
    visit[cur]=true; //cur에 방문했으므로 true로 바꿔줌
    printf("%d", cur); //방문했다고 print 해줌
    for(int i=0;i<adj[cur].size();i++){ //지금 노드와 인접한 노드들을 하나씩 전부 돌아볼거임
    	dfs(adj[cur][i]); //cur와 인접한 노드들 dfs
    }
}

② STACK 방식

bool visit[MAX]; stack<int> st;

void dfs(int cur){
	st.push(cur);
    while(!st.empty()){
    	int k = st.top();
        st.pop();
        if(visit[k]) continue;
        visit[k] = true;
        for(int i = 0; i<adj[k].size(); i++)
        	st.push(adj[k][i]);
    }
}