그래프 탐색 알고리즘

전체 탐색의 경우 for 반복문으로 구현이 가능하다.

하지만, 배열을 단순히 살펴보는 것으로 문제를 풀 수 없는 경우가 있다.

 

이를 해결하기 위해 효과적인 그래프 탐색 알고리즘이 필요하다. 

 

1. 그래프 탐색 알고리즘

 

이름에서 알 수 있듯이, 주어진 상황을 그래프로 표현하여 효율적인 탐색을 한다.

이때, 효율적인 탐색으로 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 

 

그림 출처 : 위키백과(wikipedia)

깊이 우선 탐색(DFS)	너비 우선 탐색(BFS)

용어 설명

• 노드(정점): 그림의 동그라미들 
• 엣지(변) : 동그라미를 잇는 선
• 그래프 : 정점과 변으로 표현되는 구조 
• 트리 구조 : 정점과 변에 루프(한 바퀴 돌 수 있는 부분)가 없는 구조
• 탐색 : 정점을 하나씩 확인하는 것

 

2. 깊이 우선 탐색(DFS)

 

탐색 순서 : 연필 한 획 그리기와 같이 끊어지지 않고 모든 정점을 돌아다닌다고 생각

1. 최대한 왼쪽으로 깊게 정점을 탐색한다.
2. 만약, 자식 없는 정점까지 탐색하면 가장 가까운 탐색이 끝나지 않는 정점으로 돌아와 탐색을 계속 진행한다.

• 메모리 사용 시 추가된 정점 중 가장 최근 것을 이용(스택)
• 이전 정점으로 돌아와야 하기 때문

구현 방법 : 스택, 재귀 함수를 사용

int dfs(int now)
{
	if(현재 상태 now가 끝나는 조건) 
	return 현재 상태 now 값;
	
	int ret = -1;
	for(int i = 0; i < 다음 상태 개수; i++)
	{
		int next = i번째 다음 상태;
		if(next가 조건을 만족하는 경우)
		ret = max(dfs(next), ret); 
	}
	
	return ret; 
}

 

3. 너비 우선 탐색(BFS)

 

탐색 순서 :  최근 탐색한 정점의 바로 다음 단계 정점을 차근차근 탐색

1. 깊이가 얕은 순서로 왼쪽부터 차근차근 정점을 탐색한다.

• 메모리에 추가된 정점 중 오래된 것부터 차례대로 탐색(큐)
• 가까운 순서로 탐색하므로 나중에 발견된 정점은 나중에 탐색

구현 방법 : 큐, 리스트, 배열을 사용

queue<T> q;
q.push(초기 상태);
while(!q.empty())
{
	T now = q.front(); q.pop() //현재 상태 처리
	
	for(int i =0; i < 다음 상태 개수; i++)
	{
		T next = i번째 다음 상태;
		if(next를 방문했었는지 판정)
		q.push(); 
	 } 
}

 

4. 탐색 방법 선택 시 지표가 되는 요소들

 

깊이 우선 탐색을 사용하면 좋은 경우 : [대표] 피보나치 수열

• 모든 경로를 탐색하고 결과를 확인해야 하는 경우
• 문자열 등을 탐색할 때 '사전 순서로 앞에 오는 것'처럼 앞으로 검색해서 찾는 것이 빠른 경우

 

너비 우선 탐색을 사용하면 좋은 경우 : [대표] 최단 경로 문제 

• 시작 지점에서 가장 가까운 것을 구하고 싶은 경우
• 탐색 범위 자체는 넓지만 어느 정도 근처에 구하고 싶은 해가 존재하는 것을 알고 있는 경우
• 탐색 범위가 굉장히 넓으며 깊이 우선 탐색을 사용 시 스택이 대량으로 사용되는 경우