인프런 커뮤니티 질문&답변

안녕하세요 0201님 ㅎㅎ

일단은요.

int dfs(int here) {
	int child = 0;
	visited[here] = 1;
	for (int there : adj[here]) {
		if (there == del)continue;
		if (!visited[there]) {
			ret += dfs(there);
			child++;
		}
	}
	if (child == 0) return 1;
	return 0;
}

이코드는

int형 dfs를 잘 활용하고 있지 않은 코드라고 볼 수 있습니다.

왜 그러냐면 int dfs는 단순히 1 또는 0만을 반환하는 코드이고 함수의 반환값과 상관없이 전역변수로 ret을 더하고 있습니다. 즉, 반환값 자체를 이용하지 못하고 있습니다.

함수는 각각의 의미를 갖는게 좋습니다. 여기서 dfs()는 "내 노드로부터 자식노드의 수"를 반환하는 함수가 되어야 하는데 이렇게 하면 그 의미를 갖기가 힘들죠.

만약 int형으로 하실 거면 이렇게 해야 하는 것이구요.

#include<bits/stdc++.h>
using namespace std;
int n, r, temp, root;
vector<int> adj[54];
int dfs(int here){
    int ret = 0;
    int child = 0;
    for(int there : adj[here]){
        if(there == r) continue;
        ret += dfs(there);
        child++;
    }
    if(child == 0) return 1;
    return ret;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> temp;
        if(temp == -1)root = i;
        else adj[temp].push_back(i);
    }
    cin >> r;
    if(r == root){
        cout << 0 << "\n";return 0;
    }
    cout << dfs(root) << "\n";
    return 0;
}

ret을 전역변수로 선언하고 dfs함수를 ret을 계산하는 용도로만 사용하면 틀리더라구요

>> 아닙니다. 그렇게 해도 맞게 할 수 있습니다.

전역변수를 갱신하는 함수는 void형으로 만들고 해당 함수에 의미에 맞춰 ret만을 갱신하는 함수로 만들면 됩니다.

이렇게 한번 해보시겠어요?

#include<bits/stdc++.h>
using namespace std;
int n, r, temp, root;
vector<int> adj[54];
int ret;
void dfs(int here){ 
    int child = 0;
    for(int there : adj[here]){
        if(there == r) continue;
        dfs(there); 
        child++;
    }
    //cout <<"CHILD : " << child << '\n';
    if(child == 0) ret++;  
}
int main(){ 
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> temp;
        if(temp == -1)root = i;
        else adj[temp].push_back(i);
    }
    cin >> r;
    dfs(root);
    if(r == root){
        cout << 0 << "\n";return 0;
    } 
    cout << ret << "\n";
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.