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

안녕하세요 ㅎㅎ

제가 자세한 주석 달아드렸습니다. ㅎㅎ

참고해주세요. ㅎㅎ

#include <bits/stdc++.h>
using namespace std;
int n, r, tmp, root, cnt;
vector<int> adj[54];

void dfs(int here)
{
	//??????????????r = 1?? 이게 왜 들어가요?
    if (r == 1 && adj[here].size() == 1)
    {
        cnt++;
        return;
    }
	//지워지는 정점 = r continue 좋습니다. 
    for (auto i : adj[here])
    {
        if (i == r)  continue;
		//음 근데 이렇게 될 경우. 
		// a - {b} 이렇게 연결되어있는데
		// b가 삭제노드일 때 로직이 가능한가요?
		// adj[i].size() == 1이기 때문에 b로 넘어가고
		//기저사례에도 걸리지 않죠. r = 1도 아니고 
		// b는 adj[here].size() == 0이기 때문에요.  
        if (adj[i].size() == 0)  cnt++;
        dfs(i);
    }

}


int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    
    cin >> n ;
	//good
    for(int i =0 ; i < n ; i++)
    {
        cin >> tmp;
        if(tmp == -1)root = i;
        else adj[tmp].push_back(i);
    }
    //이 root를 하는 이유는. 
	// 이 로직 자체가 child를 기반으로 되어있기 
	// 때문입니다. 
	/*
	정답코드를 보면.
	    for(int there : adj[here]){
        if(there == r) continue;
        ret += dfs(there);
        child++;
    }
	이렇게 되어있죠? 
	자신의 here을 중심으로 안하기 때문에 r이 root
	인경우의 반례가 생겨버려요. 
	로직 자체가 child를 기반으로 되어있기 때문에
	그러한 반례가 있는 거고
	그걸 커버치는 로직이 필요해서 이걸 넣는거에요. ㅎㅎ
	*/
    cin >> r;
    if(r==root){
        cout << 0 << '\n';
        return 0;
    } 
    else dfs(root);
    
    cout << cnt << '\n';
    return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

제 코드 중 main이랑 dfs 부분 중 어느 부분이 잘못되어 있는 것인지 파악하고자 강사님 코드를 좀 수정해서 실험해봤는데, main에서 root 여부 일차적으로 중요한 것이라는 생각을 하게 되었습니다. 그런데, 왜 중요한지에 대해서는 잘 모르겠습니다.

제가 짠 dfs + 강사님 main 을 합쳐서 실행해본 결과, 78% 정도에서 틀렸다고 뜨는데 어느 부분에서 잘못된 것인지 모르겠습니다.. (http://boj.kr/1970b3373d2246e6ba0c1f7e10c436a8)