경로 탐색(DFS) / c / 제한시간 없음

▣ 문제

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

총 6 가지입니다.

 

▣ 입력설명

- 첫째 줄에는 정점의 수 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

 

<내 코드>

짜려다 개망함

check 배열 쓰는거 까먹음

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int map[21][21];
int check[100];
int n, m, cnt = 0;

void dfs(int x) {
	int i;
	if (x == n) {
		cnt++;
	}
	else {
		for (i = 1; i <= n; i++) {
			if (map[x][i] == 1 && check[i]==0) {
				check[i] = 1;
				dfs(i);
				check[i] = 0;
			}
		}
	}
}

int main() {
	int i;
	int a, b;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d %d", &a, &b);
		map[a][b] = 1;
	}
	check[1] = 1;
	dfs(1);

	printf("%d", cnt);
	return 0;
}

map[ ][ ]은 방향그래프를 의미하고 check[ ]는 방문을 했는지 체크하는 배열이다.

 

만약 map[ ][ ]가 '1' 이고 check[ ]가 '0'이라면 다음 dfs함수로 넘어갈 수 있다.

 

이때 5번 정점으로 들어가면 cnt++을 해준다.

 

가장 중요한 부분은 dfs( )를 나오고 check[ ]를 '0'으로 바꿔주는 코드이다.

 

스택의 자료구조로 생각해보면 dfs(5)가 될때마다 cnt++을 해주고 스택에서 dfs(i)가 끝날때마다 check[i]=0 으로 해줌으로써 다음 탐색을 할때 중복이 되지 않는다.

 

.

 

처음에 check배열을 map과 똑같은 사이즈로 만들고 시작하기도 하고 중간에 다시 check를 바꿔주는 생각을 못함.

 

stack 공부를 다시 하고 DFS 함수 흐름에 따라서 stack 변화하는걸 알아둘 필요가 있음 -> ***중요