[개념]경로 탐색(DFS, 인접리스트) / c++ / 제한시간 없음

▣ 문제

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는

총 6 가지입니다.

 

▣ 입력설명

- 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

 

▣ 출력설명

- 총 가지수를 출력한다.

 

▣ 입력 예시

5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5

 

▣ 출력 예시

6

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<vector>
using namespace std;

int visit[21];
int cnt = 0, n;
vector<int> map[30];

void dfs(int v) {
	int i;
	if (v == n) {
		cnt++;
	}
	else {
		for (i = 0; i < map[v].size(); i++) {
			if (visit[map[v][i]] == 0) {
				visit[map[v][i]] = 1;
				dfs(map[v][i]);
				visit[map[v][i]] = 0;
			}
		}
	}
}

int main() {
	int m;
	int a, b, i;

	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	visit[1] = 1;
	dfs(1);
	printf("%d\n", cnt);
	return 0;
}

그래프(Graph)를 표현하기 위해서 크게 두 가지 방법이 있다. 하나는 인접행렬, 나머지는 인접리스트이다.

 

c++에서는 vector을 사용하면 인접리스트를 쉽게 사용할수 있기 때문에 c++을 사용했다.(c에서도 할수있지만 코드가 너무 길고 복잡해짐)

 

인접리스트는 그래프의 연결구조를 vector의 배열로 표현한것이다.

 

입력 예시를 예로 들면, 다음과 같은 그림으로 표현할수 있다.

map[1]	->	2	->	3	->	4
map[2]	->	1	->	3	->	5
map[3]	->	4	->		->
map[4]	->	2	->	5	->	5
map[5]	->		->		->

adj[n]은 연결리스트의 구조와 비슷하다고 생각하면 된다. n번 정점과 연결된 노드들을 배열로써 표현할 수 있다. 이때 사용하는 함수는 .push_back(int v)이다. 이 함수를 통해서 뒤에 노드를 계속 붙일수 있다.

 

.size()함수는 해당 인접리스트에 얼마나 많은 노드들이 연결되어 있는지를 알려준다. 만약 map[1].size()를 예로 들면 map[1]에는 2,3,4라는 노드들이 연결되어있기 때문에 '3'이라는 값을 준다.

 

.

 

인접리스트를 사용하면 사용하는 간선의 수만큼만 메로리를 사용한다는 장점이 있다. 하지만 map[i][j]가 연결되어있는지를 확인하기 위해서 vector전체의 성분을 확인해야 하기 때문에 인접행렬보다 훨씬 많은 시간이 필요하다.