[c++] 경로탐색(DFS), 인접행렬(가중치 방향그래프)

인접행렬(가중치 방향그래프)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int map[21][21];
int main() {
	freopen("input.txt", "rt", stdin);
	int n, m, a, b, c, i, j;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a ,&b, &c);
		map[a][b]=c;
	}
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			printf("%d ", map[i][j]);
		}
		printf("\n");	
	}
	return 0;
}

 

 

경로탐색(DFS)

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int map[30][30], n, m, ch[30], cnt=0;
void DFS(int v){
	int i;	
	if(v==n) {
		cnt++;
		return;
	}
	else {
		for(i=1; i<=n; i++){				// line: 13
			if(map[v][i]==1 && ch[i]==0){		// line: 14
				ch[i]=1;			// line: 15
				DFS(i);				// line: 16
				ch[i]=0;			// line: 17
			}
		}
	}
}
int main() {
	int a, b, i, j;
	//freopen("input.txt", "rt", stdin);
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a][b] = 1;
	}
	ch[1]=1;
	DFS(1);
	printf("%d", cnt);
	return 0;
}

DFS를 다 이해했다고 생각했는데 경로탐색을 보면서 다시 헷갈리기 시작했다.

위 그림처럼 그려가면서 코드를 따라가보았다.

cnt는 문제에서 원하는 결과값

ch배열은 경로를 탐색하면서 지금까지 탐색된 숫자를 체크하는 용도로 선언되었으며

map 이중배열은 경로로 이어진 숫자들을 알기위해 선언되었다.

 

일단 DFS(1)로 받아서

DFS(1)함수 내에서 1~5까지 돌면서 경로로 이어져 있는지, 경로로 이어져 있더라도 이미 지나온 경로가 아닌지를 체크한다.

 

line 13

- 매개변수로 받은 v값이 1부터 5까지 돌면서 해당 숫자와 경로로 이어져 있는지 체크하기 위해 선언

line 14

- map[v][i]은 v값에서 i값으로 가는 경로가 있는지 있다면 1, 없다면 0을 나타냄

- ch[i]은 v~i 경로가 지나온 경로라면 1, 지나온 경로가 아니라면 0을 나타냄

line 15

- line 14가 참이라면 ch[i]에 이 경로를 지나겠다는 의미로 ch[i]에 1을 넣음

line 16

- 경로에 추가를 시키고 i를 다시 DFS함수에 전달해서 v로 만들고 v와 연결된 다른 경로들을 찾는다.

line 17

- 경로를 탐색하고 돌아오면 ch[i]=0 해주어서 탐색되지 않은 경로로 만들어 준다.