백준 1068 - 트리(C++)

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

1068번: 트리

그래프 탐색을 이용하는 문제입니다.

노드를 하나 지웠을 때, 리프 노드를 구하는 문제입니다.

 

시작 노드를 찾은 뒤, 시작 노드에서 그래프 탐색을 시작해줍니다.

탐색 노드와 연결된 노드 중, 연결되지 않는 노드로 이동해 다음 노드로 계속 이동해줍니다.

더 이상 이동할 수 없는 노드로 도착하면, 리프 노드 갯수를 1 증가해줍니다.

여기서, 지워진 노드가 연결되어 있어도 이동할 수는 없으니 이때도 리프 노드를 하나 증가해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
using namespace std;

int N;
vector<int> connect[51];
int start;
int Del;
int check[51];

int bfs(){
    int cnt = 0;
    queue<int> q;
    check[start] = 1;
    q.push(start);
    while(!q.empty()){
        int x = q.front();
        int node = 0;
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(xx == Del) continue;
            node++;
            if(check[xx] == 1) continue;
            check[xx] = 1;
            q.push(xx);
        }
        if(node == 0) cnt++;
    }
    return cnt;
}

void solve(){
    if(start == Del) cout << "0";
    else cout << bfs();
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++){
        int x;
        cin >> x;
        if(x == -1) start = i;
        else connect[x].push_back(i);
    }
    cin >> Del;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요