탐색

일반적인 탐색

DFS

개념

: dfs는 깊이 우선 탁색(Depth First Search)로 루트 노드 (혹은 선택한 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완전하게 탐색하는 방법이야!!

흔히 잘 알려진 미로를 탐색하는 문제로 예를 들어보자면, dfs로 미로탐색을 구현할 경우 한방향으로 갈 수 있을 때 까지 계속해서 들어갔다가 더이상 갈 곳이 없을 때 재귀함수가 풀리면서 이전 위치로 이동하게 되고 해당 위치에서 또 갈 수 있는 방향을 탐색해서 있다면 해당 방향으로 쭈욱 갈 수 있는 만큼 가고, 또 어디로도 못가는 상황이 되었다면 재귀가 풀리면서 이전 위치에서 다음 방향을 보고 이런식으로 진행이 되는거야. 정말 말 그대로 깊이 우선 탐색이지.

특징

그래프 탐색시에는 노드를 방문한 여부를 체크하는 장치 필요
그래프를 인접행렬로 구현한 경우 O(V^2)의 시간복잡도
그래프를 인접리스트로 구현한 경우 O(V+E)의 시간복잡도
일반적으로 재귀를 이용해 구현하며 재귀이기에 스택으로도 구현할 수 있어

BFS

개념

: BFS 즉 너비우선탐색은 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회방법이야! 위에서 예로든 미로를 다시 예로 가져와보면, 이번에는 출발점에서 갈 수 있는 인접한 이웃 위치를 먼저 탐색하고 이동해. 이동했다면 또 해당 위치에서는 자신의 위치에서 인접한 이웃 위치를 탐색해서 갈 수 있는 곳을 가고.. 이렇게 현재 출발점에서 바로 이웃한 위치 즉 노드들을 탐색해 나가는 방식이 너비우선탐색이야.

특징

방문한 노드들을 차례로 꺼내면서 가까운 노드들을 탐색하기 위해 큐 자료구조를 사용해
그래프를 인접행렬로 구현한 경우 O(V^2)의 시간복잡도
그래프를 인접리스트로 구현한 경우 O(V+E)의 시간복잡도

최단거리 탐색 알고리즘

다익스트라

개념

: 하나의 시작점에서 하나의 도착점으로 가는 최단 경로를 구하기 위한 알고리즘이야. 이때 주의할 점은 음수 간선이 있으면 안돼!! 그럼 돌아갈수록 비용이 작아지는 마술에 빠져버리거든…

그래서 과정을 이야기하자면 처음 거리를 나타내주기 위한 배열을 정의한 다음 초기에는 MAX 값으로 셋팅을 해놔. 그리고 시작점에 해당하는 정보를 셋팅해. 위의 distance[출발점] = 0 셋팅과 동시에 priority queue에 출발점 정보를 넣는거지.

그 이후 큐에서 노드 정보를 꺼내어 그 다음 노드를 봤을 때 distance[다음노드]와 (현재까지 비용 + 이동 비용) 을 따졌을 때 이동하는 것이 효율적일 경우 해당 노드를 방문처리 (distance 배열 update 및 priority queue에 push) 해줘. 이를 queue가 빌 때 까지 반복하면 되는거지.

코드

struct Data {
	int start;
	int end;
	int cost;

	Data(int a, int b, int c) {
		start = a;
		end = b;
		cost = c;
	}

	bool operator<(const Data &b)const{
		return cost>b.cost;
	}
};

int Dijkstra(vector< vector<Data> > m) {
	priority_queue<Data> pq;

	vector<int> distance(N+1, 2147000000);
	distance[1] = 0;
	pq.push(Data(1,1,0));

	while(!pq.empty()) {
		int now = pq.top().end;
		int cost = pq.top().cost;
		pq.pop();

		if(distance[now] < cost)
			continue;

		for(int i=0 ; i<m[now].size() ; i++) {
			Data nextData = m[now][i];
			int nextNode = nextData.end;
			int nextCost = cost + nextData.cost;

			if(distance[nextNode] > nextCost) {
				distance[nextNode] = nextCost;
				pq.push(Data(now, nextNode, nextCost));
			}

		}
	}

	return distance[N];
}

시간복잡도

우선순위 큐 사용시 O(ElogE)
사용안할 시 O(V^2)

벨만포드

개념

: 벨만포드 또한 다익스트라처럼 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘이야. 다익스트라와는 다르게 가중치가 음수일 때도 사용할 수 있어!! 하지만 당연히 얻는게 있으면 잃는 것도 있겠지… 다익스트라에 비해 느려!! 그래서 가중치가 모두 양수라면 다익스트라를 사용하는 것이 좋아

벨만포드는 겨쳐서 갈 수 있는 모든 경우를 본다고 생각하면 될 것 같애. 즉 시작점부터 시작해서 1번만에 갈 수 있는 곳, 2번만에 갈 수 있는 곳, 3번만에 갈 수 있는 곳 …. N-1번만에 갈 수 있는 곳을 계산하는거야!!

그리고 각각의 경우마다 갈 수 있는 곳을 본다는 것은 즉 경우마다 엣지 수만큼 본다는 것이지

코드

for(i=1; i<=n; i++){
	dist[i]=2147000000;
}
dist[1]=0;

for(i=1; i<n; i++){
	for(j=0; j<Ed.size(); j++){
		int s=Ed[j].s;
		int e=Ed[j].e;
		int w=Ed[j].val;
		if(dist[s]!=2147000000 && dist[s]+w<dist[e]){
			dist[e]=dist[s]+w;
		}
	}
}

: 바깥 FOR문은 N-1번 실행돼! 왜냐?? 한 정점에서 다른 정점으로 가는 것은 맥시멈 잡아도 N-1이거든!! 그럼 N-1번 돌고나서 한번 더 돌렸는데 최소 비용으로 릴렉스 되는 상황이 발생한다면?? 그건 음의 사이클이 존재하는 거야

시간복잡도

O(VE)

플로이드 와샬

개념

: 플로이드 와샬은 위의 두 알고리즘과는 다르게 모든 정점에서 모든 점점으로의 최단경로를 구하는 알고리즘이야.

모든 쌍(정점들 간)을 표현하는 2차원 배열을 선언한 후 이를 통해 다이나믹 프로그래밍 방식으로 각 정점들 간의 거리를 타나내는 배열의 칸들을 채워나가!

코드

for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(dis[i][j]>dis[i][k]+dis[k][j]){
					dis[i][j]=dis[i][k]+dis[k][j];
				}
			}
		}
	}

시간복잡도

O(V^3)

최소신장트리 (MST)

Union & Find

개념

: 공통 원소가 없는 상호 배타적인 부분 집합 들로 나눠진 원소들에 대한 정보를 저장하기 위한 알고리즙이야.

Disjoint-Set 알고리즘이라고도 해.

과정은 간단해. 노드들의 정보가 주어져있다고 가정해볼게. 두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는거야!!

Find를 통해 선택된 노드의 부모노드를 찾을 수 있고

각 노드에 대해 Find 연산을 수행한 후 결과 값이 같다면 같은 그래프에, 다르다면 Union 연산을 통해 묶어주면 끝이야!!

코드

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a]=b;
}

크루스칼

개념

: 크루스칼 알고리즘은 최소신장트리를 만들기 위한 알고리즘이야. 즉 가장 적은 비용으로 모든 노드를 연결하게 해주는 알고리즘이지.

크루스칼은 간선의 비용이 가장 작은 내용( 출발점, 도착점, 비용)부터 하나씩 확인하며 해당 내용을 받아들였을 때 사이클이 생기는지 안생기는지 여부를 판단하며 연결해줘나가!!

즉 사이클이 안생긴다면 Union연산을 통해 연결시켜주고 그렇지 않다면(사이클이 생긴다면) 무시하는 방식인거지

코드

sort(Ed.begin(), Ed.end());

for(i=0; i<m; i++){
	int fa=Find(Ed[i].s);
	int fb=Find(Ed[i].e);

	if(fa!=fb){
		res+=Ed[i].val;
		Union(Ed[i].s, Ed[i].e);
	}
}

시간복잡도

O(ElogE)야. 크루스칼은 결국은 정렬알고리즘을 수행하는 시간만큼 시간복잡도가 걸리게 되므로 O(NlogN)의 시간복잡도를 가진 정렬 알고리즘을 사용했다 가정하면 위처럼 시간복잡도가 계산이 되어져

프림

개념

: 크루스칼처럼 최소신장트리를 구성하기 위한 알고리즘이야. 하지만 그 방법이 차이가 있어.

프림은 시작 정점을 정해 그 시작 정점부터 출발하면서 신장트리 집합을 단계적으로 확장해나가!!

우선순위큐에 간선의 비용을 기준으로 데이터를 넣고 빼면서 시작점부터 인접한 노드들을 시작하여 작은 비용의 간선부터 뽑으면서 붙여나가는거지!

코드

Q.push(Edge(1, 0));

while(!Q.empty()){
	Edge tmp=Q.top();
	Q.pop();
	int v=tmp.e;
	int cost=tmp.val;
	if(ch[v]==0){
		res+=cost;
		ch[v]=1;

		for(i=0; i<map[v].size(); i++){
			if(ch[map[v][i].first]==0){
				Q.push(Edge(map[v][i].first, map[v][i].second));
			}
	  }
	}
}

시간복잡도

인접행렬 사용할 경우 O(V^2)
이진 힙을 사용할 경우 O(ElogV)