[C++] 경로 탐색(인접리스트, DFS) ⭐

📄문제

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

위 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다.

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

 

⬇️ 입력

첫째 줄에는 정점의 수 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

 

📝 풀이

#include <iostream>
#include <vector>
using namespace std;

static int cnt = 0;
bool* visited;

void DFS(vector<int> map[], int N, int v)
{
	visited[v] = true;

	if (v == N)
		++cnt;
	else
		for (int i = 0; i < map[v].size(); ++i)
			if (!visited[map[v][i]])
			{
				DFS(map, N, map[v][i]);
				visited[map[v][i]] = false;
			}
}

int main()
{
	int N, M, f, t;
	scanf_s("%d %d", &N, &M);
	vector<int>* map = new vector<int>[N + 1];
	visited = new bool[N + 1];

	for (int i = 1; i <= N; ++i)
		visited[i] = false;

	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d", &f, &t);
		map[f].push_back(t);
	}

	DFS(map, N, 1);

	printf("%d", cnt);
}

• 2차원의 인접 행렬을 만들지 않고 vector<int> 자료구조를 이용하여 f에서 출발하는 노드가 도착하는 노드 t를 map[f].push_back(t)를 통해 구현하였습니다.
• 재귀문에서 현재 위치한 v에서 다음 이동 구역을 검색할 때 map[v]가 가지고 있는 원소를 반복하여 검사할 수 있습니다.