[C++]백준 25511번 값 k인 트리 노드의 깊이

📌문제 링크

---

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

📌문제 설명

---

주어지는 간선의 정보를 토대로 트리를 구성한 뒤, dfs탐색으로 k값을 가지고 있는 정점의 깊이를 출력해주면 됩니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> graph[100001]; // 그래프를 저장할 벡터 배열
bool visited[100001]; // 방문 여부를 체크할 배열
int n, k, value[100001]; // n: 노드 수, k: 찾고자 하는 값, value: 각 노드의 값

// 입력 함수
void input(){
    cin >> n >> k; // 노드 수와 찾고자 하는 값을 입력받음
    for(int i = 0; i < n - 1; i++){
        int p, c; cin >> p >> c; // 부모 노드와 자식 노드를 입력받음
        graph[p].push_back(c); // 그래프에 간선 추가
    }
    for(int i = 0; i < n; i++){
        cin >> value[i]; // 각 노드의 값을 입력받음
    }
}

// 깊이 우선 탐색 함수
void dfs(int idx, int depth){
    visited[idx] = true; // 현재 노드를 방문 처리
    if(value[idx] == k){ // 현재 노드의 값이 k와 같다면
        cout << depth; // 깊이를 출력
        return; // 함수 종료
    }
    for(auto it : graph[idx]){ // 현재 노드의 인접 노드를 탐색
        if(!visited[it]){ // 인접 노드가 방문되지 않았다면
            dfs(it, depth + 1); // 인접 노드로 이동, 깊이를 1 증가
        }
    }
}

// 문제 해결 함수
void solve(){
    input(); // 입력 받기
    dfs(0, 0); // 루트 노드부터 깊이 우선 탐색 시작
}

int main(){
    ios::sync_with_stdio(0); // 입출력 속도 향상
    cin.tie(0); // 입력 스트림과 출력 스트림을 분리
    solve(); // 문제 해결 함수 호출
    return 0; // 프로그램 종료
}