[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 N, M, cnt = 0;
static vector <vector<bool>> arr;
static vector <bool> visited;

void DFS(int v)
{
	// 방문 TRUE
	visited[v] = true;

	// v(방문지)가 N - 1(마지막 노드)이라면?
	if (v == N - 1)
	{
		cnt++;
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			// 더 방문할곳이 있다면?
			if (arr[v][i] == 1 && visited[i] == 0)
			{
				DFS(i); // 해당 구역에 더 찾아가기 (DFS)
				visited[i] = false; // 해당 구역에서 빠져나오면, 해당 구역 방문은 false로 전환
			}
		}
	}
}
int main()
{
	scanf_s("%d %d", &N, &M);

	arr = vector <vector<bool>>(N, vector<bool>(N, false));
	visited = vector<bool>(N, false);

	int f, t; // from, to
	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d", &f, &t);

		arr[f - 1][t - 1] = true;
	}

	// 0번(맨 처음)부터 방문 시작
	DFS(0);

	printf("%d", cnt);
}

• DFS를 활용하여 가능한 모든 방문 가능한 노드를 검사합니다.
• 만약 검사를 하였을 때, 도착한 노드가 N-1이라면, 문제 조건에 맞는 답이기때문에 cnt를 1씩 증가시킵니다.