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 으로 다시 바꾸어주어야한다.