*(백준BAEKJOOB )* 1068 트리

문제 출처

 

1068번: 트리

 

 

 

문제 풀이

 

시행착오

 

 

 

 

코드

bfs 풀이 1번째

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<int> v[51]; // 각 노드들의 연결성을 저장하는 vector
queue<int> q; // bfs를 위한 큐

int visited[51]; // 방문 여부를 저장하는 배열                                        //리졀트              //차일드
int N, root_idx, result, child; // N: 트리의 노드 수, root_idx: 루트 노드의 인덱스, result: 리프 노드 수, child: 현재 노드의 자식 노드 수

void bfs(int start) {
    visited[start] = 1; // 시작 노드 방문 표시
    q.push(start); // 시작 노드를 큐에 push

    while (!q.empty()) { // 큐가 비어있을 때까지 반복
        int root = q.front(); // 큐에 있는 노드 중 가장 앞에 있는 노드를 root로 지정
        q.pop(); // root 노드를 큐에서 pop

        child = 0;
        for (int i = 0; i < v[root].size(); i++) { // 현재 노드의 자식 노드에 대한 반복문
            if (!visited[v[root][i]]) { // 현재 노드가 방문한 적이 없는 자식 노드인 경우
                child++; // 자식 노드 수를 1 증가
                visited[v[root][i]] = 1; // 해당 노드를 방문 표시
                q.push(v[root][i]); // 해당 노드를 큐에 push
            }
        }
        if (child == 0) result++; // 자식 노드가 없으면 해당 노드는 리프 노드이므로, 결과값(result)을 1 증가시킨다.
    }
}

int main() {
    cin >> N; // 트리의 노드 수 입력
    for (int i = 0; i < N; i++) {
        int data;
        cin >> data; // 부모 노드 입력
        if (data == -1) root_idx = i; // 루트 노드의 인덱스 저장
        else v[data].push_back(i); // 해당 노드와 부모 노드와의 연결성(간선) 추가
    }

    int cut; // 끊어낼 노드의 번호
    cin >> cut; // 끊어낼 노드의 번호 입력
    visited[cut] = 1; // 끊어낼 노드는 방문 처리

    if (!visited[root_idx]) bfs(root_idx); // 루트 노드가 방문한 적이 없으면 bfs 수행
    printf("%d\n", result); // 리프 노드의 수 출력

    return 0;
}

+

 

 

2번째 dfs

 

 

설명

bfs 개념과 dfs 개념 다시 잡기