[백준] 1068번: 트리의 부모 찾기

Kim Yuhyeon·2024년 2월 4일

알고리즘 + 자료구조

목록 보기

155/161

문제

https://www.acmicpc.net/problem/1068

접근 방법

각 부모마다 자식 리스트 만들기

리프 노드 리스트 만들기

누군가의 부모이면 리프노드 = false

지운 노드가 루트 노드이면 무조건 0 리턴

처음 리프 노드의 개수 구하기

지운 노드의 자식 리스트를 방문하기

리프노드면 처음에 구한 리프노드의 개수 빼기

리프노드가 아니면 자식 리스트를 방문하기 (반복)

지운 노드의 부모가 리프노드인지 체크하기

지운 노드 부모의 자식 리스트에서 지운 노드를 제거 했을 때, 자식 리스트 개수가 0개이면 리프노드 개수 더하기

반례

지운 노드의 부모가 리프노드가 될 경우

2
-1 0
1
정답 : 1

9
-1 0 0 5 2 4 4 6 6
4
정답 : 2

2
1 -1
0
정답 : 1

5
1 2 3 4 -1
3
정답 : 1

루트 노드를 삭제하면 0이 나와야한다.

2
1 -1
1
정답 : 0

1
-1
0
정답 : 0

풀이


#include <iostream>
#include <queue>
#include <string.h> // memset
#include <algorithm>

#define MAX 50

using namespace std;

int N;
int parent[MAX];
int deletedNode;

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void input() {
    cin >> N;

    for(int i=0; i<N; i++) {
        cin >> parent[i];
    }

    cin >> deletedNode;

    return; 
}

int solve(int N, int parents[], int deletedNode) {
    int answer = 0;

    vector<int> childs[MAX];
    bool isLeafNode[N];
    int rootNode;
    memset(isLeafNode, true, sizeof(isLeafNode));

    // 연결
    for(int child=0; child<N; child++) {
        if (parents[child] != -1) {
            isLeafNode[parents[child]] = false; // 부모 -> 리프 노드 아님
            childs[parents[child]].push_back(child); // 부모 - 자식
        } else {
            rootNode = child;
        }
    }

    // 루트 노드를 삭제하면 0이 나와야한다. 
    if (deletedNode == rootNode) {
        return answer;
    }

    // 리프 노드 개수
    for(int i=0; i<N; i++) {
        if (isLeafNode[i]) answer++;
    }
    
    queue<int> q;
    q.push(deletedNode);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        if (isLeafNode[curr]) {
            answer--;
        } else {
            for(int child : childs[curr]) {
                q.push(child);
            }
        }
    }

    // 지운거의 부모
    int target = parents[deletedNode];
    if (find(childs[target].begin(), childs[target].end(), deletedNode) != childs[target].end()) {
        childs[target].erase(remove(childs[target].begin(), childs[target].end(), deletedNode));
    }
    if (childs[target].size() == 0) answer++;

    return answer;
}

void output(int answer) {
    cout << answer << '\n';
}

int main() {
    fastIO();
    input();
    output(solve(N, parent, deletedNode));
}