백준 1068번 트리

문제 링크입니다: https://www.acmicpc.net/problem/1068

parent 배열의 first는 부모노드 번호를 저장하고 second는 자신이 leaf인지 여부를 저장하도록 했습니다.

사실 true일 때 leaf이면 더 직관적이겠지만 배열을 생성할 때 default 값은 false이므로 false일 때 leaf이도록 하였습니다.

ancestor 배열은 자신의 부모를 포함한 모든 조상을 저장하게 하여 자신의 조상 중 deleteNode가 있을 경우 삭제되었다고 판단하여 다시 leaf가 아니라고 판단하였습니다.

조상을 파악한 뒤 deleteNode를 제외한 모든 노드의 부모를 다시 확인하는 이유는 삭제된 노드의 부모는 leaf라고 main 문에서 판단하였는데 삭제된 노드의 부모가 다른 자식이 있을 수도 있기 때문에 한번 더 확인했습니다.

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 50;

 

int N, deleteNode;

pair<int, bool> parent[MAX]; //부모노드, (true: leaf가 아니다, false: leaf)

vector<int> ancestor[MAX];

 

int countLeaf(void)

{

        //조상 중에 deleteNode가 있으면 삭제된 노드이므로

        for(int i=0; i<N; i++)

                 for (int j = 0; j < ancestor[i].size(); j++)

                         if (ancestor[i][j] == deleteNode)

                                 parent[i].second = true; //leaf가 아니다

 

        //삭제된 노드 제외하고 다시 자식 여부 파악

        for (int i = 0; i < N; i++)

                 if(i!=deleteNode)

                         parent[parent[i].first].second = true; //leaf가 아니다

 

        //leaf 노드 개수 센다

        int cnt = 0;

        for (int i = 0; i < N; i++)

                 if (parent[i].second == false)

                         cnt++;

 

        return cnt;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

        {

                 cin >> parent[i].first;

                 parent[parent[i].first].second = true;

        }

 

        //모든 조상 파악

        for (int i = 0; i < N; i++)

        {

                 int curParent = parent[i].first;

                 while (curParent != -1)

                 {

                         ancestor[i].push_back(curParent);

                         curParent = parent[curParent].first;

                 }

        }

 

        cin >> deleteNode;

        parent[deleteNode].second = true;  //삭제된 노드는 leaf가 아니다

        parent[parent[deleteNode].first].second = false; //삭제된 노드의 부모는 leaf이다

 

        cout << countLeaf() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~