인프런 커뮤니티 질문&답변
작성한 질문수
2-R 데이터 저장
작성
·
387
0
http://boj.kr/1c07c3f4f76347e791816ea1d051396b
위의 코드에서
5 -1 0 0 1 1 0
다음과 같은 테스트케이스를 넣어주면 deleteChildren()에서 1번 노드가 들어갈때 데이터가 온전히 전달이 안됩니다... 확인해보니 1번 노드에서는 자식이 2개여야 하는데 0개로 나옵니다.
deleteChildren를 호출하기전에는 2개로 잘 나오는데 이유가 뭘까요..? 아래 사진은 deleteChildren을 호출하기전 데이터 사진입니다. 
deleteChildren(node& nd) 으로 해도 데이터가 안넘어가지더라구요... 우선은 node가 아닌 int idx를 받아 함수 안에서 tree[idx] 이렇게 직접 찾게 바꿔서 해결은 했습니다만 데이터가 제대로 안넘어가는 이유가 너무 궁금합니다!!
답변 5
0
안녕하세요 자르트님 ㅎㅎ
일단 Node를 기반으로 트리를 구축한다는 것은 알겠는데 조금 이상한 부분이 있습니다.
cin >> n;
for (int i = 0; i < n; i++) {
int parent;
cin >> parent;
tree.push_back(node(i, parent));
}
for (int i = 0; i < tree.size(); i++) {
for (int j = 0; j < tree.size(); j++) {
if (tree[i] == tree[j]) continue;
if (tree[j].parent == tree[i].num) {
tree[i].children.push_back(tree[j]);
}
}
}Node를 가지는 tree에다가 node를 넣습니다. 그리고 다시 그 노드를 기반으로 tree[i]의 children을 채워놓는데요. 이게 좀 복잡한 코드라고 생각하는데요. 그냥 i번째 parent에다가 등록을 하면 되지 않을까요?
그리고 질문하신 내용에 답을 드리면요.
번호가 1인 nd의 경우 제가 설정한 전역변수의 tree에선 자식의 수가 2개여야 하는데 사진과 같이 deleteChildren 함수 안에서 호출될 경우 nd의 자식 값이 0으로 돼 있습니다!(2가 나오는 것이 정상입니다)
함수로 넘겨주고 이런 과정에서 전역변수의 tree랑 함수안에서 다루는 tree랑 값에 괴리가 생기는 것 같습니다
>> 음.. 저 지우는 부분의 로직이 이상한게 있습니다. 전역변수로 설정한 값을 기반으로 erase()는 다 통합니다.
이런식으로 고쳐야 합니다.
주석 달았습니다. 참고부탁드립니다.
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;
int n, m, ret;
class node {
public:
int num;
int parent;
vector<node> children;
node(int num, int parent) {
this->num = num;
this->parent = parent;
}
bool operator==(node nd)
{
if (this->num == nd.num)return true;
return false;
}
};
vector<node> tree;
void deleteChildren(node nd) {
// 기저사례를 앞단에!
if(nd.children.size() == 0){
// 해당 부모로부터 올라가서 child를 지우는 로직이 필요.
return;
}
for(node a : nd.children){
deleteChildren(a);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int parent; cin >> parent;
tree.push_back(node(i, parent));
}
for (int i = 0; i < tree.size(); i++) {
for (int j = 0; j < tree.size(); j++) {
if (tree[i] == tree[j]) continue;
if (tree[j].parent == tree[i].num) {
tree[i].children.push_back(tree[j]);
}
}
}
// 디버깅
// for(int i = 0; i < tree.size(); i++){
// cout << i << "\n";
// for(node t : tree[i].children){
// cout << t.num << " ";
// }
// cout << '\n';
// }
// cout << "::::::\n";
cin >> m;
for (int i = 0; i < tree.size(); i++) {
if (m == tree[i].num) {
//해당 노드의 children을 다 지운다.
deleteChildren(tree[i]);
// 해당 노드를 지우는 로직이 필요.
break;
}
}
for (int i = 0; i < tree.size(); i++) {
if (tree[i].children.size() == 0) ret++;
}
cout << ret;
}
사실 Node 라는 구조체를 쓰는 것 자체가 어렵기 때문에 해설코드를 보면 인접리스트로 구현을 했는데요.
제가 한번 자르트님을 위해서 Node 클래스를 사용해서 구현해봤습니다.
이게 정석이라고 보시면 되며 주석 달았으니 확인하시면서 공부하시면 될 것 같습니다.
#include <bits/stdc++.h>
using namespace std;
class Tree {
struct Node {
int parent, child;
};
public:
Node node[51];
int root, size;
Tree() {
for (int i = 0; i < 51; i++) {
node[i].parent = -12010;
node[i].child = 0;
}
}
void add(int i, int a) {
// root일 경우
if (a == -1) {
root = i;
node[i].parent = -1;
}
else {
node[i].parent = a;
node[a].child++;
}
}
// 해당 부모노드의 child를 감소시킨다.
// 지워진 노드의 parent값을 -12010로 놓는다.
void del(int i) {
node[node[i].parent].child--;
node[i].parent = -12010;
}
// leaf 노드의 수를 구하는 함수.
int get_leaf() {
int ret = 0, temp;
for (int i = 0; i < size; i++) {
if (node[i].child != 0) continue;
temp = i;
while (true) {
temp = node[temp].parent;
if (temp == -1 || temp == -12010)
break;
}
// 지워진 노드가 아님을 확인함.
if (temp == -1)ret++;
}
return ret;
}
void set_size(int n) {
size = n;
}
};
int main() {
int size, dele,temp;
Tree tree;
scanf("%d", &size);
tree.set_size(size);
for (int i = 0; i < size; i++) {
scanf("%d", &temp);
tree.add(i, temp);
}
scanf("%d", &dele);
tree.del(dele);
printf("%d", tree.get_leaf());
}
또 질문 있으시면 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다.
감사합니다.
0
2번 질문에 대한 답 입니다.
트리 자체는 잘 생성되나 함수로 넘겨주고 이런 과정에서 전역변수의 tree랑 함수안에서 다루는 tree랑 값에 괴리가 생기는 것 같습니다. 같은 전역변수를 쓰는데 왜 이런지 모르겠습니다...
0
안녕하세요 큰돌님! 큰돌님께서 올려주신 사진 2가지의 경우에 모두 nd의 번호가 1로 제대로 나옵니다. 번호가 1인 nd의 경우 제가 설정한 전역변수의 tree에선 자식의 수가 2개여야 하는데 사진과 같이 deleteChildren 함수 안에서 호출될 경우 nd의 자식 값이 0으로 돼 있습니다!(2가 나오는 것이 정상입니다)
복사와 참조 문제인 것 같았는데 도저히 모르겠습니다..
0
안녕하세요 자르트님 ㅎㅎ
질문이 좀 이해가 안되서 확인을 좀 하자면요.
1.node가 변경이 안된다.
vector<node> tree;
void deleteChildren(node nd) {이렇게 nd를 넘겼을 때 변경이 안된다.
또한 이것도 안된다.
vector<node> tree;
void deleteChildren(node &nd) {2.이렇게 트리를 생성했는데 잘 안된다.
cin >> n;
for (int i = 0; i < n; i++) {
int parent; cin >> parent;
tree.push_back(node(i, parent));
}
for (int i = 0; i < tree.size(); i++) {
for (int j = 0; j < tree.size(); j++) {
if (tree[i] == tree[j]) continue;
if (tree[j].parent == tree[i].num) {
tree[i].children.push_back(tree[j]);
}
}
}
이것들이 궁금하신게 맞나요?
0
안녕하세요, 인프런 AI 인턴이에요.
코드와 설명을 통해 확인해보니 deleteChildren() 함수에서 데이터가 제대로 전달되지 않는 이유에 대해 궁금하신 것 같습니다.
데이터가 올바르게 전달되지 않는 원인은 코드에 디버깅을 통해 정확히 확인할 필요가 있습니다. 하지만 현재 제공된 코드만으로는 문제를 파악하기 어렵습니다. 디버깅을 위해서는 코드의 일부가 더 필요하며, 상세한 내용을 파악하기 어렵습니다.
코드의 특정 부분에서 문제가 발생하는 것으로 보이지만, deleteChildren() 함수 자체의 로직, 전체 코드의 흐름 등을 고려해야 합니다. 주어진 코드와 함께 전체 코드를 공유해주시면 좀 더 정확한 도움을 드릴 수 있을 것 같습니다.
더불어, 문제 해결을 위해 다른 변형된 접근법을 사용하셨다는 것을 언급하셨는데, 이로 인해 데이터가 올바르게 전달되었다면 문제 해결에는 성공한 것으로 볼 수 있습니다.
아쉽게도 현재로서 이유를 정확히 파악하기 어렵기 때문에, 제공된 내용을 통해 더 자세한 도움을 드리기는 어렵습니다.
더 나은 도움을 드리기 위해 코드와 관련된 전체 내용을 공유해주시면 감사하겠습니다. 또한 다른 질문이 있거나 추가적인 도움이 필요하신 경우에는 언제든지 말씀해주세요. 좋은 하루 되세요!