• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

2-R 반례 궁금합니다.

23.11.02 15:16 작성 조회수 96

0

#include <bits/stdc++.h>
using namespace std;

int N;
map<int, vector<int>> mp;
int tmp, d, ret;

void removeAll(int key){
    // if not leaf node -> recursive remove
    if(!mp[key].empty()) {
        for(int c: mp[key]) removeAll(c);
    }
    // erase itself
    mp.erase(key);
    
}

int main(){
    cin >> N;
    
    // make graph
    for(int i = 0; i < N; i++){
        mp[i];
        cin >> tmp;
        if (tmp != -1) mp[tmp].push_back(i);
    }
    // input node to be deleted 
    cin >> d;
    removeAll(d);

    if (mp.size() == 1) ret = 1;
    else if (mp.size() == 0) ret = 0;
    else {
        // for all key in map
        for(auto it: mp) {
            int key = it.first;
            // if the remaining value empty => plus
            if (mp[key].empty()) ret++;
        }
    }

    cout << ret;
}

다음과 같이 map과 재귀를 풀어서 1068번 트리 문제를 풀었는데, 어디가 오답인지 감이 안옵니다.

course-thumbnail

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2-N

강의실 바로가기

답변 1

답변을 작성해보세요.

0

큰돌님의 프로필

큰돌

지식공유자

2023.11.03

안녕하세요 it님ㅎㅎ

map을 이용하셔서 잘하셨네요

다만, 저렇게 할 경우 지워진 노드의 부모 노드로부터 지우는 코드가 필요합니다.

제가 좀 다듬어 봤는데요.

이렇게 해보시겠어요? 

#include <bits/stdc++.h>
using namespace std;

int N;
map<int, vector<int>> mp;
int tmp, d, ret;

void removeAll(int key){ 
    if(!mp[key].empty()) {
        for(int c: mp[key]) removeAll(c);
    } 
    mp.erase(key);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
     
    for(int i = 0; i < N; i++){
        mp[i];
        cin >> tmp;
        if (tmp != -1) mp[tmp].push_back(i);
    }
 
    cin >> d;
    removeAll(d); 
    for(auto& it: mp) {
        it.second.erase(remove(it.second.begin(), it.second.end(), d), it.second.end());
    }

    ret = 0;
    for(auto it: mp) {
        if (mp[it.first].empty()) ret++;  
    }

    cout << ret;
    return 0;
}

 

 

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

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

감사합니다.

강사 큰돌 올림.

 

이 글과 비슷한 Q&A