1068 트리

백준 1068 트리 https://www.acmicpc.net/problem/1068

트리가 존재할때 어떤 노드하나를 지웠을 경우 남은 트리에서 리프(leaf)노드의 개수를 구하는 문제이다.

인접행렬을 만들어 연결된 점들을 저장한후에 dfs탐색으로 제거될 노드를 제외하고 탐색을 시키며 리프노드의 개수를 구한다.

#include <cstdio> int arr[51][51]; int N, M, root; int ans = 0; void dfs(int num){     int cnt = 0;     if (num == M)                //지워야하는 노드에 들어갔을 경우 반환         return;     for (int n = 0; n < N; n++){         if (num != n && arr[num][n] == 1 && n != M){        // num -> n으로 연결된 곳으로 dfs             cnt++;             dfs(n);         }     }     if (cnt == 0)        //leaf노드일 경우         ans++;     return; } int main(){     scanf("%d", &N);     for (int n = 0; n < N; n++){         int data;         scanf("%d", &data);         if (data == -1)             root = n; Colored by Color Scripter

cs