그래프 탐색 DFS

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;
int map[51][51], check[10], path[10], p1;

void DFS(int cur, int fin){
	if(cur==fin){
		for(int i=0; path[i]!=0; i++){
			printf("%d ",path[i]);
		}
		printf("\n");
	}
	else{
		for(int i=1; i<=fin; i++){
			if(map[cur][i]==1 && check[i]==0){
				path[p1++] = i;  
				check[i] = 1;
				DFS(i,fin);
				check[i] = 0;
				
				p1--;
				path[p1] = 0;
			}
		}		
	}
	
}


int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n, m, i, j, a,b;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a][b]=1;
	}
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			printf("%d ",map[i][j]);
		}
		printf("\n");
		
	}
	check[1] = 1;
	path[p1++] = 1;
	DFS(1,n);
	
	return 0;	
}

 

output

-- 그래프 -- 
0 1 1 1 0
1 0 1 0 1
0 0 0 1 0
0 1 0 0 1
0 0 0 0 0

 

-- 탐색 path--
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5