53. 경로 탐색(DFS)

 

 

▣ 입력예제 

 

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>
#include <algorithm>

using namespace std;

int map[30][30], ch[30], cnt = 0, n;

void DFS(int v)
{
	if (v == n)  // * 재귀가 종료 지점에 왔느냐?
	{
		cnt++;
	}
	else
	{
		for (int i = 1; i <= n; ++i)
		{
			if (map[v][i] == 1 && ch[i] == 0)
			{
				ch[i] = 1; // 방문 체크
				DFS(i);
				ch[i] = 0; // 호출 스택 빠져 나오면 방문 체크 해제
			}
		}
	}
}

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

	cin >> n >> m; // 정점, 간선 개수

	for (int i = 1; i <= m; ++i)
	{
		cin >> a >> b;
		map[a][b] = 1; // 가중치 그래프 ( 인접 행렬 )
	}

	ch[1] = 1; // 방문지점은 다시는 안가기 위해 체크배열을 둔다.
	DFS(1);
	cout << cnt;
}