인프런 커뮤니티 질문&답변
작성한 질문수
선생님 2-R 문제 질문드립니다.
작성
·
287
0
선생님 안녕하세요.
이번에 2-R 문제를 푸는데 예제와 제가 만든 예제들도 다 통과하는데 결과는 78% 정도에서 계속 실패가 뜨는데 왜 그런지 잘 모르겠습니다.. ㅜㅜ
우선 제가 푼 방식은 삭제 노드부터 시작해 그 밑의 모든 자식 노드들에 -1을 넣어. 최후에는 size==0인 노드의 갯수를 세주는 방식으로 풀었습니다. 또한 루트 로드만 남았을 경우에는 그 루트노드가 리프노드임을 감안하여 코드를 작성했습니다. 혹시 어떤 부분이 틀렸는지 봐주실 수 있나요?
#include <bits/stdc++.h>
using namespace std;
vector<int> 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;i++){
cin>>n;
if(n==-1) r=i;
else v[n].push_back(i);
}
cin>>num;
if(num==r){
cout<<0<<"\n";
return 0;
}
else{
dfs(num);
for(int i=0;i<N;i++){
if(v[i].size()==0) cnt+=1;
}
cout<<cnt<<"\n";
}
return 0;
}답변 3
0
음.. 지금 보면 로직이 "혼동"이 됩니다. 자, 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();
}
}
감사합니다.
0
아. 제가 푼 방식은 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이 되는 과정입니다.
최대한 제가 생각한걸 표현해봤는데 맞는지 모르겠네요.. ㅜㅜ
0
안녕하세요. ㅎㅎ
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를 변경시켜야 하는데 그런 것도 없어서요.
아하..!! 어디에서 실수 했는지 깨달았습니다 빠른 답변 감사합니다!!