[백준] 1068번_트리 C++
in Study on Coding Test
bfs와 dfs를 활용하는 문제
정답제출코드(리팩토링 후)
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
class Node
{
public:
vector<Node*> Child;
int data;
bool visited = false;
public:
Node() {};
~Node()
{
int len = Child.size();
for (int i = 0; i < len; ++i)
{
if (Child[i] != nullptr)
{
delete Child[i];
Child[i] = nullptr;
}
}
Child.clear();
}
};
Node* Root;
vector<Node*> NodeList;
int LeafCount = 0;
vector<int> inputList;
void bfsDelete(int target)
{
if (Root->data == target)
{
// 타겟이 루트일 경우 동적할당 해제 및 nullptr로 전환
delete Root;
Root = nullptr;
return;
}
queue<Node*> que;
que.push(Root);
Root->visited = true;
while (!que.empty())
{
Node* cur = que.front();
que.pop();
cur->visited = true;
int childSize = cur->Child.size();
for (int i = 0; i < childSize; ++i)
{
if (cur->Child[i] != nullptr && !cur->Child[i]->visited)
{
que.push(cur->Child[i]);
}
if (cur->Child[i]->data == target)
{
// 자식 목록에서 지워버려야함.
delete cur->Child[i];
cur->Child[i] = nullptr;
cur->Child.erase(cur->Child.begin() + i);
// 큐 초기화, 메모리 초과 방지
que = queue<Node*>();
return;
}
}
}
}
void dfs()
{
stack<Node*> st;
st.push(Root);
Root->visited = true;
while (!st.empty())
{
Node* cur = st.top();
st.pop();
cur->visited = true;
int childSize = cur->Child.size();
// 자식이 없다는 것은 리프노드라는 이야기.
if (childSize == 0)
LeafCount++;
for (int i = 0; i < childSize; ++i)
{
if (cur->Child[i] != nullptr && !cur->Child[i]->visited)
{
st.push(cur->Child[i]);
}
}
}
}
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
int _input;
cin >> _input;
// 객체 생성 및 데이터 주입
Node* n = new Node;
n->data = i;
NodeList.push_back(n);
inputList.push_back(_input);
if (_input == -1)
Root = n;
}
// 자식 - 부모 연결결
int inputlen = inputList.size();
int Nodelen = NodeList.size();
for (int i = 0; i < inputlen; ++i)
{
for (int j = 0; j < Nodelen; ++j)
{
if (NodeList[j]->data == inputList[i])
{
NodeList[j]->Child.push_back(NodeList[i]);
}
}
}
// 삭제할 노드의 데이터 입력
int DeleteData;
cin >> DeleteData;
// 노드 삭제
bfsDelete(DeleteData);
// 방문여부 초기화
for (int i = 0; i < Nodelen; ++i)
{
if (NodeList[i] != nullptr)
NodeList[i]->visited = false;
}
// 루트노드가 삭제된 경우 그냥 dfs 생략하고 LeafCount = 0 출력
if (Root != nullptr)
dfs();
cout << LeafCount;
// 동적할당 해제
if (Root != nullptr)
{
delete Root;
Root = nullptr;
}
return 0;
}
소멸자에 자식들의 동적할당을 모두 해제해주는 코드를 추가하였다.
이전에 제출한 코드는 메모리 누수가 발생할 우려가 있어서 리팩토링을 진행하였다.
그리고 추가로 bfs를 마치는 과정에서 메모리 초과가 발생하지 않도록 큐를 초기화 하도록 했다.
이 문제를 찾을 때 까지 수많은 메모리 초과라는 결과물을 보았다..
정답제출코드(이전)
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
class Node
{
public:
vector<Node*> Child;
int data;
bool visited = false;
};
Node* Root;
vector<Node*> NodeList;
int LeafCount = 0;
vector<int> inputList;
void bfsDelete(int target)
{
if (Root->data == target)
{
Root = nullptr;
return;
}
queue<Node*> que;
que.push(Root);
Root->visited = true;
while (!que.empty())
{
Node* cur = que.front();
// cout << cur << "Current" << '\n';
que.pop();
cur->visited = true;
int childSize = cur->Child.size();
for (int i = 0; i < childSize; ++i)
{
if (cur->Child[i] != nullptr && !cur->Child[i]->visited)
{
que.push(cur->Child[i]);
}
if (cur->Child[i]->data == target)
{
// 검증용
// cout << cur->Child[i] << " Delete\n";
// cout << cur << "Parent" << '\n';
// 자식 목록에서 지워버려야함.
cur->Child.erase(cur->Child.begin() + i);
return;
}
}
}
}
void dfs()
{
stack<Node*> st;
st.push(Root);
Root->visited = true;
while (!st.empty())
{
Node* cur = st.top();
// cout << cur << "Current" << '\n';
st.pop();
cur->visited = true;
int childSize = cur->Child.size();
// 자식이 없다는 것은 리프노드라는 이야기.
if (childSize == 0)
LeafCount++;
for (int i = 0; i < childSize; ++i)
{
if (cur->Child[i] != nullptr && !cur->Child[i]->visited)
{
st.push(cur->Child[i]);
}
}
}
}
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
int _input;
cin >> _input;
// 객체 생성 및 데이터 주입
Node* n = new Node;
n->data = i;
NodeList.push_back(n);
inputList.push_back(_input);
// 검증용
// cout << n << ' ' << n->data << '\n';
if (_input == -1)
Root = n;
}
// 자식 - 부모 연결결
int inputlen = inputList.size();
int Nodelen = NodeList.size();
for (int i = 0; i < inputlen; ++i)
{
for (int j = 0; j < Nodelen; ++j)
{
if (NodeList[j]->data == inputList[i])
{
// 검증용
// cout << "Parent : " << NodeList[j]->data << " Child : " << NodeList[i]->data << '\n';
NodeList[j]->Child.push_back(NodeList[i]);
}
}
}
// 삭제할 노드의 데이터 입력
int DeleteData;
cin >> DeleteData;
// 노드 삭제
bfsDelete(DeleteData);
// 방문여부 초기화
for (int i = 0; i < Nodelen; ++i)
{
if (NodeList[i] != nullptr)
NodeList[i]->visited = false;
}
// 루트노드가 삭제된 경우 그냥 dfs 생략하고 LeafCount = 0 출력
if (Root != nullptr)
dfs();
cout << LeafCount;
// 동적할당 해제
for (int i = 0; i < Nodelen; ++i)
{
if (NodeList[i] != nullptr)
delete NodeList[i];
}
return 0;
}
백준 알고리즘 문제를 풀면서 처음으로 클래스를 활용하였다.
솔직히 이 방법밖에 떠오르지도 않고..
객체지향적 사고를 키우고 싶어서 클래스를 써서 풀었다.
Node* n = new Node;
객체는 위 코드를 통해서 생성하였다.
동적할당과 포인터를 활용하지 않고,
Node n;
이렇게 생성하니 dfs를 탐색할 때 자식노드목록이 정상적으로 전달되지 않는 오류가 발생하였다.
동적할당을 이용하고, 포인터를 함수에 전달함으로써 dfs 중에도 자식노드목록이 전달되도록 조치하였다.
void bfsDelete(int target)
{
if (Root->data == target)
{
Root = nullptr;
return;
}
queue<Node*> que;
que.push(Root);
Root->visited = true;
while (!que.empty())
{
Node* cur = que.front();
// cout << cur << "Current" << '\n';
que.pop();
cur->visited = true;
int childSize = cur->Child.size();
for (int i = 0; i < childSize; ++i)
{
if (cur->Child[i] != nullptr && !cur->Child[i]->visited)
{
que.push(cur->Child[i]);
}
if (cur->Child[i]->data == target)
{
// 검증용
// cout << cur->Child[i] << " Delete\n";
// cout << cur << "Parent" << '\n';
// 자식 목록에서 지워버려야함.
cur->Child.erase(cur->Child.begin() + i);
return;
}
}
}
}
그리고 삭제하고 싶은 노드를 삭제할 땐 bfs탐색을 이용했다.
해당 부모를 찾아내고, 그 부모의 자식목록에서
타겟 자식 노드를 삭제하는데 좀 애를 먹었다.
// 노드 삭제
int len = NodeList.size();
for (int i = 0; i < len; ++i)
{
if (NodeList[i]->data == DeleteData)
delete NodeList[i];
}
자식노드를 삭제하는 코드는 원래 이거였는데,
동적해제만 시켜주는 것이지 부모와 자식노드의 관계를 끊어버리는 것이 아니기 때문에
아래 오답제출코드의 반례에 해당하는 오류가 발생했다.
그리고 메모리 릭을 방지하기 위해서는 아래 코드는 필수.
// 동적할당 해제
for (int i = 0; i < len; ++i)
{
if (NodeList[i] != nullptr)
delete NodeList[i];
}
오답제출코드
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Node
{
public:
vector<Node*> Child;
int data;
bool visited = false;
};
vector<Node*> NodeList;
int LeafCount = 0;
void dfs(Node* start)
{
// 루트노드가 삭제된 경우 그냥 리턴
if (start == nullptr)
return;
stack<Node*> st;
st.push(start);
start->visited = true;
while (!st.empty())
{
Node* cur = st.top();
st.pop();
cur->visited = true;
int childSize = cur->Child.size();
// 자식이 없다는 것은 리프노드라는 이야기.
if (childSize == 0)
LeafCount++;
for (int i = 0; i < childSize; ++i)
{
if (cur->Child[i] != nullptr && !cur->Child[i]->visited)
{
st.push(cur->Child[i]);
}
}
}
}
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
int _input;
cin >> _input;
// 객체 생성 및 데이터 주입
Node* n = new Node;
n->data = i;
NodeList.push_back(n);
if (_input == -1)
continue;
int len = NodeList.size();
for (int j = 0; j < len; ++j)
{
if (NodeList[j]->data == _input)
{
NodeList[j]->Child.push_back(n);
}
}
}
// 삭제할 노드의 데이터 입력
int DeleteData;
cin >> DeleteData;
// 노드 삭제
int len = NodeList.size();
for (int i = 0; i < len; ++i)
{
if (NodeList[i]->data == DeleteData)
delete NodeList[i];
}
dfs(NodeList[0]);
cout << LeafCount;
// 동적할당 해제
for (int i = 0; i < NodeList.size(); ++i)
{
if (NodeList[i] != nullptr)
delete NodeList[i];
}
return 0;
}
반례
5
-1 0 1 1 1
1
// 원하는 값 : 1
// 출력된 값 : 3
루트노드(0)의 자식노드가 1이고, 1이 나머지 자식노드 3개를 가지고 있는 구조이다.
여기서 1을 삭제했더니 원하는 값은 1이 나와야 하는데, (0 혼자만 있기 때문)
출력되는 값은 3이다.
아무래도 0의 자식 목록에 1이 그대로 존재하기 때문에 그런 것 같았다.
그 자식목록에서 자식을 지우는 데에는 위에 있는 bfs를 활용하였다.
오답제출코드2
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
class Node
{
public:
vector<Node*> Child;
int data;
bool visited = false;
};
vector<Node*> NodeList;
int LeafCount = 0;
void bfsDelete(Node* start, int target)
{
// 루트노드가 삭제된 경우 그냥 리턴
if (start == nullptr)
return;
queue<Node*> que;
que.push(start);
start->visited = true;
while (!que.empty())
{
Node* cur = que.front();
// cout << cur << "Current" << '\n';
que.pop();
cur->visited = true;
int childSize = cur->Child.size();
for (int i = 0; i < childSize; ++i)
{
if (cur->Child[i] != nullptr && !cur->Child[i]->visited)
{
que.push(cur->Child[i]);
}
if (cur->Child[i]->data == target)
{
// 검증용
// cout << cur->Child[i] << " Delete\n";
// cout << cur << "Parent" << '\n';
// 자식 목록에서 지워버려야함.
cur->Child.erase(cur->Child.begin() + i);
return;
}
}
}
}
void dfs(Node* start)
{
// 검증용
// cout << start << "Start" << '\n';
// 루트노드가 삭제된 경우 그냥 리턴
if (start == nullptr)
return;
stack<Node*> st;
st.push(start);
start->visited = true;
while (!st.empty())
{
Node* cur = st.top();
// cout << cur << "Current" << '\n';
st.pop();
cur->visited = true;
int childSize = cur->Child.size();
// 자식이 없다는 것은 리프노드라는 이야기.
if (childSize == 0)
LeafCount++;
for (int i = 0; i < childSize; ++i)
{
if (cur->Child[i] != nullptr && !cur->Child[i]->visited)
{
st.push(cur->Child[i]);
}
}
}
}
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
int _input;
cin >> _input;
// 객체 생성 및 데이터 주입
Node* n = new Node;
n->data = i;
NodeList.push_back(n);
// 검증용
// cout << n << ' ' << n->data << '\n';
if (_input == -1)
continue;
int len = NodeList.size();
for (int j = 0; j < len; ++j)
{
if (NodeList[j]->data == _input)
{
NodeList[j]->Child.push_back(n);
}
}
}
// 삭제할 노드의 데이터 입력
int DeleteData;
cin >> DeleteData;
// 노드 삭제
bfsDelete(NodeList[0], DeleteData);
// 방문여부 초기화
int len = NodeList.size();
for (int i = 0; i < len; ++i)
{
NodeList[i]->visited = false;
}
dfs(NodeList[0]);
cout << LeafCount;
// 동적할당 해제
for (int i = 0; i < len; ++i)
{
if (NodeList[i] != nullptr)
delete NodeList[i];
}
return 0;
}
반례
3
1 -1 1
1
// 원하는 값 : 0
// 출력된 값 : 2
설마 테스트케이스에 -1(루트노드)가 나중에 나오는 경우가 있을까? 생각했다.
설마가 사람잡았네..
내가 제출한 오답코드에서는 루트노드가 나중에 나오는 경우에는 올바르게 작동하지 않는다.
그래서 루트노드를 전역변수에다가 저장하도록 조치하였다.
그리고 bfs와 dfs의 시작점을 전역변수에 있는 루트에서 시작하도록 만들고,
오답코드에서는 전달을 해줬던 노드의 주소 인자값을 없앴다.
// 수정 후
Node* Root;
void bfsDelete(int target)
void dfs()
