🙇‍♀️경로 탐색(DFS : 인접리스트 방법)

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

아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는

image

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

총 6 가지입니다.

▣ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 

그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

▣ 출력설명
총 가지수를 출력한다.

▣ 입력예제 1 
5 9
1 2 
1 3
1 4 
2 1 
2 3 
2 5 
3 4 
4 2 
4 5 

▣ 출력예제 1
6

🚀풀이

이전의 경로 탐색은 인접 행렬 방식이였는데 인접 리스트로 다시 푸는 것.

아래와 같은 코드다.

인접 리스트 만들어주기

int n, m, res = 0;
vector<vector<int>> vec;
vector<bool> visited;
void setting()
{
	cin >> n >> m;
	vec = vector<vector<int>>(n + 1);
	visited = vector<bool>(n + 1);

	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
	}
}

DFS 인접리스트

void DFS(int here)
{
	if (here > n)
		return;
	if (here == n)
	{
		res++;
	}

	for (int there = 0; there < vec[here].size(); ++there)
	{
		if (visited[vec[here][there]])
			continue;

		visited[here] = 1;
		DFS(vec[here][there]);
		visited[here] = 0;
	}
}

강의를 보고 코드가 많이 다르면 추가 할 예정.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, res = 0;
vector<vector<int>> vec;
vector<bool> visited;
void setting()
{
	cin >> n >> m;
	vec = vector<vector<int>>(n + 1);
	visited = vector<bool>(n + 1);

	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
	}
}

void DFS(int here)
{
	if (here > n)
		return;
	if (here == n)
	{
		res++;
	}

	for (int there = 0; there < vec[here].size(); ++there)
	{
		if (visited[vec[here][there]])
			continue;

		visited[here] = 1;
		DFS(vec[here][there]);
		visited[here] = 0;
	}
}

void solve()
{
	setting();

	DFS(1);

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고