반응형
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 |