[백준] #1068 트리 :: 잡다한 프로그래밍
반응형

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

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

www.acmicpc.net

1. 해결방법

BFS를 통하여 해결하였고, 트리를 Vector에 저장하는 방법을 몰라서 찾아보았다


2. 코드

트리문제 유형을 공부해보지 못해서 고생했다. 특히 비교하는 부분 코드가 수정할 수 있을거 같으므로 나중에 다시 풀어볼 예정이다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N;
int M;
int D;
int root;
int result = 0;
queue<int> q;
vector<int> t[51];

void BFS() {
    if (root == D) return;
    q.push(root);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int i = 0; i < t[node].size(); i++) {
            if (t[node][i] != D) {
                q.push(t[node][i]);
                if (!t[t[node][i]].size() || (t[t[node][i]].size() == 1 &&t[t[node][i]][0] == D)){
                    result++;
                }
            }
            else {
                if (root == node && t[node].size() <=1) result++;
            }
        }
    }
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> M;
        if (M == -1) root = i;
        else t[M].push_back(i);
    }
    cin >> D;
    BFS();
    cout << result;
    return 0;
}
반응형

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] #1197 램프  (0) 2020.05.08
[백준] #1034 램프  (0) 2020.04.13
[백준] #1012 유기농 배추  (0) 2020.04.06

+ Recent posts