CodingTest Exam/[C++] Algorithm Study
64. 경로 탐색(DFS) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆
HongongHB
2023. 8. 19. 17:53

#include <stdio.h>
using namespace std;
int n, count = 0;
int map[21][21];
int ch[21];
void FindRoute(int x)
{
if(x == n)
{
count++;
}
else
{
for(int i = 1; i <= n; i++)
{
if(map[x][i] == 1 && ch[i] == 0)
{
ch[i] = 1;
FindRoute(i);
ch[i] = 0;
}
}
}
}
int main()
{
int m, a, b;
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d %d", &a, &b);
map[a][b] = 1;
}
ch[1] = 1;
FindRoute(1);
printf("%d", count);
return 0;
}
1. 노드의 개수 n, 간선의 개수 m, 인접 행렬 map, 해당 간선이 왔다간 간선인지 체크할 배열 ch, 문제의 조건을 만족하는 경우의 수 count, 간선의 방향을 결정할 a, b 를 선언한다.
2. FindRoute(int x) 재귀함수를 이용하여 간선을 타고 이동하면서 원하는 노드에 도착하는지의 여부를 확인한다.
3. 1에서부터 출발(FindRoute(1)) 하기 때문에 ch[1] = 1로 할당한다.
4. 만약 노드 1 -> 노드 2로 갔다면 ch[2] = 1로 해준다. 이 때, call by Reference 이기 때문에 해당 재귀함수가 종료되면 ch[2] = 0 으로 다시 바꾸어주어야한다.
