[알고리즘] 백준 1068

백준 1068번 트리

해결 과정 요약

dfs 함수에 리프를 만나면 ret값을 늘리는 과정을 추가한다.
dfs 함수에 해당 노드가 삭제된 노드인지 확인하는 과정을 추가한다.
출력하기 전에 삭제되는 노드의 부모노드가 자식을 1개 가진다면 ret값 1부터 증가시킨다. 하지만 그 부모노드가 루트라면 0부터 증가시켜야 한다.

if(tree[tree[delNode].parent].child.size() == 1 &&
       tree[delNode].parent != 0) ret = 1;
dfs(0);

풀이

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

struct Node{
    int parent;
    vector<int> child;
};

int N,input,ret,delNode;
Node tree[55];
int parent[55];
int visited[55];

void dfs(int idx){
    if(visited[idx] == 1 || idx == delNode) return;
    visited[idx] = 1;
    int t_size = (int)tree[idx].child.size();
    if(!t_size) ret++;
    for(int i=0; i<t_size; i++) dfs(tree[idx].child[i]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> input;
        tree[i+1].parent = input+1;
        tree[input+1].child.push_back(i+1);
    }
    cin >> delNode; delNode++;
    if(tree[tree[delNode].parent].child.size() == 1 &&
       tree[delNode].parent != 0) ret = 1;
    dfs(0);
    cout << ret;
    
    return 0;
}

트러블슈팅

• 삭제되는 노드의 부모노드가 자식을 1개 가진다면 출력값에 +1를 해주어야 하는 것을 생각하지 못했다.
  • 구조체 Node 안에 parent를 저장하는 방식으로 해결.

코멘트

틀린 코드를 빠르게 수정하기 위해 구조체를 사용해 지지고 볶다보니 코드가 난잡해졌다..