확실히 난이도가 급격하게 올라갔다.. 이제는 그림판 혹은 종이와 펜없이 머리속으로만 생각하고 코드를 작성하는게 어려워졌다.
우선 한 2~3일에 걸쳐서 공부하고, 작성한 코드를 리뷰삼아 올려보려고 한다.
지금까지 군대에서 사지방 연등을 통해 올렸던 내용들이 나중에 다시 보려고 혹은 무엇인가를 했다는 것을 남기기 위해 업로드했었지만, 지금은 진짜로 다시 한번 리뷰를 하고, 이것을 부디 까먹지 않기 위해 업로드를 한다.
우선 기본적인 DFS를 통해 부분집합을 출력하는 코드부터 작성해보겠다.
코드는 다음과 같다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
int Level[11]={0,};
void DFS(int x){
if(x==N+1){
for(int i=1; i<=N; i++){
if(Level[i]==1){
cout<<i<<" ";
}
}
cout<<""<<endl;
return;
}
else{
Level[x]=1;
DFS(x+1);
Level[x]=0;
DFS(x+1);
}
}
int main(){
cin>>N;
DFS(1);
}여기 코드에서 핵심은
Level[x]=1;
DFS(x+1);
Level[x]=0;
DFS(x+1);
이 부분인데, 왼쪽 서브트리와 오른쪽 서브트리를 들어가기전에, LEVEL이라는 배열에다가 지금까지 탐색해온 결과를 저장하고, 다시 재귀를 들어가는 것이다.
이때까지만해도 재귀함수를 통한 탐색에 대해 명확하게 이해하지 못했다.
그리고 어제부터 풀었던 문제는 다음과 같다.
합이 같은 부분집합을 구하는 DFS 문제이다.
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 "YES"를 출력, 그렇지 않으면 "NO"를 출력하는 것이다.
예를 들어서 {2, 4, 6, 5, 7} 가 입력됐을 때, {2, 4, 6}과 {5, 7} 로 두 부분집합의 합이 똑같으므로 "YES"를 출력한다.
우선 위에 기본적인 부분집합을 출력하는 DFS 코드와 비슷한 경로로 접근했다.
어떠한 정보를 넘겨주고, 왼쪽트리부터 탐색을 하고, 다시 어떠한 정보를 넘겨준 후 오른쪽 트리를 탐색하는..
근데 이게 재귀함수를 이용하다보니, 정보를 넘겨주는 부분에 있어서 민감(?)한 부분이 있었고, 그렇기 때문에 좀 더 안전한 방법을 택해야했다.
우선 코드는 다음과 같다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int num[11]={0,};
int total;
int N;
bool flag = false;
void DFS(int level, int sum){
if(sum>total/2){
return;
}
if(flag==true){
return;
}
if(level==N+1){
if(sum==total-sum){
flag = true;
}
return;
}
else{
DFS(level+1, sum+num[level]);
DFS(level+1, sum);
}
}
int main(){
cin>>N;
for(int i=1; i<=N; i++){
cin>>num[i];
total += num[i];
}
DFS(1, 0);
if(flag){
cout<<"YES";
}
else{
cout<<"NO";
}
}우선 새롭게 알게된 사실
DFS안에 존재하는 return 은, 더 이상 탐색을 할 필요가 없는 경우를 나타낸다.
간단한 부분집합을 구하는 코드에서도 그랬고, 위 코드에서 그랬듯이 더 이상 탐색을 할 필요가 없는 경우 return을 해버린다.
sum이 total의 반을 넘어버리면, 더이상 탐색을 해봤자 무의미하다.(sum에 계속해서 더해질텐데, 그러면 의미가 없으니까)
그리고 flag가 이미 true로 바뀌어버렸을 때 더이상 탐색을 하지 않아도 된다.
또한 level이 N+1가 되었을 때, flag가 true로 바뀌면 탐색을 중지해도 된다.
근데 이게 탐색을 그만 한다는게 아예 그만한다는 것은 아니고, 더이상 서브트리로 내려가지 않는 것을 의미한다. 물론 뭐 break같은 것을 걸어서 탐색을 중지해버릴수도 있겠지만 적어도 위 코드에서는 그렇다.
그리고 위 코드에서는 DFS함수에다가 2개의 인자를 넘겨줬는데, 탐색하고 있는 트리의 현위치(level)와 지금까지 탐색한 트리들의 합(sum)이다.
처음에 코드를 짤 때에는 sum을 따로 넘겨주지 않고, 그냥 DFS함수 내에서 +-를 해주려고 했지만 너어어어어어무 복잡하다.. 그래서 결국에는 인자로 넘겨주는게 훠월씬 스마트한 방식이란 것을 후에 알았다.
- 요약
DFS 함수가 재귀로 굴러갈 때, 겹겹히 쌓이는 스택들의 메카니즘을 잘 이해해야 코드를 구현할 수 있다.. 아직 나도 많이 부족하기 때문에 더 많은 문제를 풀어볼 예정..
DFS(level+1, sum+num[level]);
DFS(level+1, sum);얘네 두 줄이 제일 중요한 두줄...
왼쪽으로 넘길때에는 sum을 더해주고, 그리고 다시 복귀해서 오른쪽으로 넘어갈때에는 sum을 그대로 두는 것... 심도깊은 이해가 있어야 구현할 수 있는 코드..
