선생님 2-R 문제 질문드립니다.

Question

선생님 안녕하세요. 이번에 2-R 문제를 푸는데 예제와 제가 만든 예제들도 다 통과하는데 결과는 78% 정도에서 계속 실패가 뜨는데 왜 그런지 잘 모르겠습니다.. ㅜㅜ 우선 제가 푼 방식은 삭제 노드부터 시작해 그 밑의 모든 자식 노드들에 -1을 넣어. 최후에는 size==0인 노드의 갯수를 세주는 방식으로 풀었습니다. 또한 루트 로드만 남았을 경우에는 그 루트노드가 리프노드임을 감안하여 코드를 작성했습니다. 혹시 어떤 부분이 틀렸는지 봐주실 수 있나요? #include using namespace std; vector v[52]; int N,n,num,cnt,r,temp; void dfs(int a){ while(v[a].size()>0){ temp=v[a][v[a].size()-1]; v[a].pop_back(); dfs(temp); } v[a].push_back(-1); return ; } int main(){ cin.tie(NULL); cin>>N; for(int i=0;i>n; if(n==-1) r=i; else v[n].push_back(i); } cin>>num; if(num==r){ cout<<0<<" "; return 0; } else{ dfs(num); for(int i=0;i

큰돌 · Answer

음.. 지금 보면 로직이 "혼동"이 됩니다. 자, grade님께서 말씀하신건 - 1과 제거를 같이 한다는 건데 굳이 그럴 필요가 없죠.  제거면 제거 -1이면 -1 두가지 중에 한가지만 하셔도 될 거같아요.  예를 들어 제거같은 경우는 이렇게 하면 되겠죠?    void dfs(int here){ if(adj[here].size() == 0) return; for(int there : adj[here]){ dfs(there); } while(adj[here].size()){ adj[here].pop_back(); } }   감사합니다.

grade854 · Answer

아. 제가 푼 방식은 while 문을 통해 a의 노드의 자식노드를 뒤에서부터 하나씩 탐색해주어 탐색한 자식 노드들은 .pop_back() 해주어 v[a] 사이즈를 줄여준 다음에 v[a].size()가 0이 될 시 -1값을 추가해주어 v[a].size() 가 0이 안되게 하여 size가 0인 노드들의 갯수를 검색해주는 것입니다. 예를 들어, 사이트 예제 2에서 v[0]={1,2}, v[1]={3,4}, v[2]={}, v[3]={}, v[4]={} 이므로 dfs(1)을 할 시 v[1][1]인 4를 통해 v[4]를 dfs 진행해 주고 size가 0이므로 -1을 추가해줍니다. 그리고 v[1]에서 pop_back을 통해 size를 줄입니다. 다음에는 v[1][0]인 3을 통해 v[3]을 dfs 진행해 주고 v[3]의 size가 0이므로 마찬가지로 -1을 추가해주고, v[1]에서 pop_back을 통해 size를 줄여줍니다. 이렇게 2번 진행해준 결과 v[1]의 size가 0이 되므로 v[1]에도 마찬가지로 -1을 .push_back을 해줍니다. 이 결과 v[0]={1,2}, v[1]={-1}, v[2]={}, v[3]={-1}, v[4]={-1} 이 되어 size가 0인 갯수를 세주면 1이 되므로 답이 1이 되는 과정입니다. 최대한 제가 생각한걸 표현해봤는데 맞는지 모르겠네요.. ㅜㅜ

큰돌 · Answer

안녕하세요. ㅎㅎ void dfs ( int a) { while (v[a]. size ()> 0 ){ temp=v[a][v[a]. size () -1 ]; v[a]. pop_back (); dfs (temp); } v[a]. push_back ( -1 ); return ; } 이코드가 이해가 안되는데요. 좀 더 설명해주실 수 있으실까요? 예를 들어 while문을 통해 계속해서 갱신되는 v[a].size() 를 통해 지우고 싶다면 a를 변경시켜야 하는데 그런 것도 없어서요.