22.07.10

64. 경로탐색

void DFS(int now){
	
	vector<int> v = map[now];
	
	if(now==n-1){
		answer++;
		return;
	}

	for(int i=0; i<v.size();i++){
		if(v[i]!=0&&ch[i]==0){
			ch[i]=1;
			DFS(i);
			ch[i]=0;
		}
	}	
}
	


int main(){
//	freopen("input.txt","rt",stdin);	
	
	int m;
	scanf("%d",&n);
	cin>>m;

	
	int a,b; 
	for(int i=0; i<m; i++){
		cin>>a>>b;
		map[a-1][b-1]=1;
	}
	
	ch[0]=1;
	DFS(0);
	cout<<answer;
}

기존에 지나갔던 숫자를 어떻게 판별하고 조건을 걸지에 대한 방법을 생각 못해서 결국 강의를 보았다. 사실 방법 자체는 생각해봤지만, ch로 이미 지나갔다고 표시한 것을 어떻게 다시 초기화 할 것이고 언제 초기화해야될지를 몰랐었는데, 재귀함수를 호출하고 해당 재귀함수가 완료돼었을 때, 즉 바로 다음줄에서 초기화하면 되는 것이었다.

65. 미로 탐색

경로탐색과 굉장히 유사한 문제였다. DFS는 결국 모든 경우의 수를 다 확인해보는 알고리즘인 것 같다. 하지만 모두 한 번씩 확인해볼 수 있다는 점, 또 재귀를 통해 한 번 실행 후 계속 조건을 확인하고 업데이트 할 수 있다는 점이 무지성으로 반복문을 돌리는 것보다 체계적이고 효율적이라고 생각한다.

66.경로탐색(방향그래프 인접 리스트:used Vector)

이 문제는 64번 경로탐색과 동일하지만 vector 를 이용하는 해결하는 문제였다. 인접행렬을 사용했을 때보다 장점은 사이즈가 커지면 커질수록 vector가 유리해진다. 이유는 인접행렬은 모든 데이터를 확인하지만 애초에 값을 읽을 때부터 vector로 받아서 필요한 값들만 저장한다면, vector의 사이즈만큼만 탐색하면 되고, 더 빠르게 탐색을 완료할 수 있게 된다.

67,68. 최소비용 경로탐색

vector<int> v[30], p[30];
vector<int> ch(30,1);
int n, m, answer=INT_MAX;
void DFS(int idx, int sum){
	
	if(idx==n){
		if(sum<answer){	
			answer = sum;
		}
	}
	else{
		for(int i=0;i<v[idx].size();i++){
			if(ch[v[idx][i]] != 0){
				ch[v[idx][i]]=0;
				sum+=p[idx][i];
				DFS(v[idx][i],sum);
				sum-=p[idx][i];
				ch[v[idx][i]]=1;
			}
		}
	}
}
	
int main(){
	//freopen("input.txt","rt",stdin);	

	cin>>n>>m;
	
	int a, b, c;
	for(int i=1; i<=m; i++){
		cin>>a>>b>>c;
		v[a].push_back(b);
		p[a].push_back(c);
	}
	
	ch[1]=0;
	DFS(1,0);
	cout<<answer;
}

경로탐색과 동일하지만, 비용 조건을 추가한 문제였다. sum 값을 업데이트 하는데 있어서 재귀함수 호출이 끝나면 다시 sum에 더했던 값을 빼줘야하는데 그 작업을 안 해서 계속 답이 틀리게 나왔었다.
재귀함수를 사용할 때에는 함수 호출 전과 후에 다시 설정해줘야하는 값들이 무엇인지 차분히 생각해볼 필요가 있다. 이번 경우에는 sum 값은 다음 재귀함수에 맞게 설정해서 넘겨준 것이기 때문에 끝나면 되돌려줄 필요가 있었다.