66. 경로탐색(DFS : 인접리스트 방법 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <stdio.h>
#include <vector>

using namespace std;

int n, count = 0;
int ch[21];
vector<int> map[21];

void FindRoute(int x)
{
	if(x == n)
		count++;
	else
	{
		for(int i = 0; i < map[x].size(); i++)
		{
			int temp = map[x][i];
			if(ch[temp] == 0)
			{
				ch[temp] = 1;
				FindRoute(temp);
				ch[temp] = 0;
			}
		}
	}
}

int main()
{
	int m, a, b;
	scanf("%d %d", &n, &m);
	
	for(int i = 1; i <= m; i++)
	{
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	
	ch[1] = 1;
	FindRoute(1);
	
	printf("%d", count);
	return 0;
}

1. 인접리스트(adjency List) : 그래프와의 연결관계를 vector의 배열 로 표현한 것이다.  

 

• 전체 노드 개수: V 간선의 개수: E

[장점]

• 실제 연결된 노드만 저장
• 모든 vector의 원소의 개수 합 = 간선의 개수
• 전체 노드 탐색 시 시간복잡도 O(E)

[단점]

• 노드가 서로 연결되어있는지 확인하는데 오래 걸린다. 인접 행렬은 adj[i][j]의 값이 1인지 확인하면 연결된 것을 알지만 인접 리스트의 경우는 adj[i]가 j를 원소로 갖는지 확인해봐야한다. 시간복잡도 O(V)

 

 

!! vector 선언시 매우 중요한 차이점 !!

1. vector<int> a

- 크기가 0인 vector 선언

2. vector<int> a(5);

- 크기가 5인 vector 선언

3. vector<int> a[5];

- 크기가 5인 vector 배열 a(크기가 0) 선언