메모이제이션이란 재귀함수를 호출하는 과정에서 이미 호출된 적이 있는 값들은 저장해놨다가 그대로 꺼내서 쓰는 방법이다.
이 문제를 봤을 때 그냥 for문 돌려서 풀면 되는 거 아닌가? 라고 생각했는데, 재귀를 사용하는 이유는 먼저 가독성이 높아진다는 장점이 있다. 그리고 더 큰 이유로 단순 반복보다 훨씬 확장가능성이 높다.
int b, cnt[1000];
vector<int> v[1000];
void DFS(int a){
if(v[a].empty()) return;
else{
for(int i=0; i<v[a].size(); i++){
if(v[a][i]==b){
cout<<"YES";
exit(0);
}
else if(cnt[v[a][i]]==0)
{
cnt[v[a][i]]=1;
DFS(v[a][i]);
}
}
}
}
int main(){
//freopen("input.txt","rt",stdin);
int n, m, a;
cin>>n>>m;
for(int i=1; i<=m; i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
cin>>a>>b;
DFS(a);
cout<<"NO";
return 0;
}
내가 문제를 푼 방식은 이중벡터에 인덱스마다 직접적으로 주어진 친구관계에 대한 정보를 담는다.
예를 들면, 1 3, 1 5 가 데이터로 주어지면 1번 인덱스에 3,5를 추가한다.
그 후 cnt벡터로 방문한 수인지 확인하면서 재귀함수를 통해 서로 연관된 친구인지 확인하는 방법을 사용했다.
이 방법이 꽤 명확하긴 하지만 데이터가 커지면 굉장히 비효율적일 것 같다는 생각이 든다.
그래서 강의에서 보여준 방법을 사용한다면 좋겠지만, 솔직히 그 방법을 과연 혼자서도 떠올리고 응용할 수 있을지는 조금 의문이다. 강의에서는 Union&Find 알고리즘을 사용했다.
int unf[1001];
int find(int k){
if(unf[k]==k) return k;
else return unf[k] = find(unf[k]);
}
void Union(int a, int b){
a = find(a);
b = find(b);
if(a!=b) unf[a] = b;
}
int main(){
//freopen("input.txt","rt",stdin);
int n, m, a, b;
cin>>n>>m;
for(int i=1; i<n; i++){
unf[i]=i;
}
for(int i=1; i<=m; i++){
cin>>a>>b;
Union(a,b);
}
cin>>a>>b;
a = find(a);
b = find(b);
if(a==b) cout<<"YES";
else cout<<"NO";
return 0;
}
Union&Find 알고리즘을 사용한 코드이다.
초기에 unf배열을 인덱스와 인덱스마다 저장된 데이터의 값이 같도록 설정해둔다.
이후 친구 사이인 두 수에 해당하는 인덱스에 저장된 값을 통일시키는데, 이 과정에서 find함수가 이용된다.
find 함수는 인덱스에 저장된 데이터와 인덱스가 일치하면 그대로 return 하고 그게 아니라면 이 조건을 만족하는 수가 나올 때까지 재귀함수를 호출하면서 동일한 집합에 속한 인덱스에 저장된 수들을 통일하는 매커니즘이라고 이해했다.