개요
-
입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다. -
출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
접근 방식
첫번째 시도(틀림)
-
처음엔 tree 배열을 생성 후 루트 노드를 1로 잡고, 들어오는 노드들을
1씩 더해서 저장해줬다.
heap자료구조를 구할때와 비슷하게
왼쪽 자식 노드값은 부모노드 인덱스*2,
오른쪽 자식 노드값은 부모노드 인덱스 *2 +1
로 표현하기 위함이다.for (int i = 1; i <= Nodes; i++) { cin >> ParentNodeInput; if (ParentNodeInput == -1) tree[1] = 1; //-1이 아니라면 else { //부모 노드값의 왼쪽자식이 이미 채워져있다면 오른쪽 자식 채움 if (tree[(ParentNodeInput + 1) * 2] == 1) { tree[(ParentNodeInput + 1) * 2 + 1] = 1; } //안채워져있다면 왼쪽 자식 채움 else tree[(ParentNodeInput + 1) * 2] = 1; } -
하지만 이렇게 인덱스로 접근하니 문제가 의도하는 바와는 달랐다.
예제 4와 같이
9
-1 0 0 2 2 4 4 6 6
4이렇게 들어오면 문제의 의도는
이런식으로 트리가 구성되어있지만
내 방식대로면 노드가 무조건 왼쪽부터 채워지므로 tree배열에서
빈 부모노드에 자식이 달려있는 꼴로 되었다.
두번째 시도(틀림)
-
그 후 부모 배열과 자식 배열을 생성후 해당 배열에 값을 입력받는 식으로
구현을 하였는 데,int parent[51]; int leftChildren[51]; int rightChildren[51];for (int i = 0; i < Nodes; i++) { cin >> parentNodeInput; //루트값이 아니고 if (parentNodeInput != -1) { //입력받은 부모노드의 왼쪽 자식 배열값이 0이면 해당 배열에 현재 인덱스값 넣어줌 if (leftChildren[parentNodeInput] == 0) leftChildren[parentNodeInput] = i; //입력받은 부노노드 왼쪽 자식 배열값이 0이 아니면 오른쪽 자식 배열에 현재 인덱스값 넣음 else rightChildren[parentNodeInput] = i; //현재인덱스의 부모값은 입력값으로 지정해줌 parent[i] = parentNodeInput; } }이 방식대로 하면 지워질 서브트리의 루트노드값을 받을 때,
뭐 leftChildren[parent[deleteNode]] 값이 deleteNode인지
rightChildren[parent[deleteNode]]값이 deleteNode인지 확인후
해당 값을 0으로 바꿔서 지워주면 된다. -
위의 방식으로 풀때 처음엔 모든 값에 0으로 초기화 했었다.
하지만 index 0이 무조건 root가 아니라서 4 이런 값이 root가 되어버리면 0값에서 바로 패스해 버려서 오답이 나왔다.
따라서 -1로 초기화해줬다.
-> 하지만 계속 틀려서 검색해본결과
근본적인 문제가 있었는데 트리가 무조건 이진트리가 아닐수도 있었다. -
따라서 그냥 벡터로 해결하였다.
세번쨰 시도(맞음)
-
2차원 벡터를 생성한 후, 주어진 노드들을
해당 값의 인덱스와 부모값을 서로 연결해줬다.
root,delete노드인 값은 따로 저장을 해줬다.for (int i = 0; i < Nodes; i++) { cin >> parentNodeInput; //루트값이 아니고 if (parentNodeInput != -1) { adj[i].push_back(parentNodeInput); adj[parentNodeInput].push_back(i); } else rootNode = i; } //삭제할 노드값 cin >> deleteNode; //만약 루트 노드 삭제시 바로 답 출력 if (deleteNode == rootNode){ cout << 0; return; } -
그 후 해당 루트 노드에서 dfs방식을 통해 리프노드가 몇개인지
구하였다. searchTree()함수엔 초기인수로 root노드 값이 들어간다.//DFS방식으로 int SearchTree(int Node) { int leafNodes = 0,childrenCnt=0; //각 노드마다 방문 체크 visited[Node] = true; //해당 노드에 연결된 노드들에 대해 for (int elem : adj[Node]) { //방문 했다면 패스 if (visited[elem]) continue; //해당 값이 지워진노드라면 패스 if (elem == deleteNode) continue; //부모 제외하고 자식 몇개인지 체크용 childrenCnt++; //위의 조건을 통과했다면 리프노드값을 재귀를 통해 구함 leafNodes += SearchTree(elem); } //delete노드가 자식이라도 위에서 걸러짐. 따라서 자식 값이 0개면 리프노드이므로 1 리턴 if (childrenCnt==0) return 1; //리프노드가 아니면 지금까지의 리프노드값 return return leafNodes; }
전체 코드
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> adj;
vector<bool> visited;
int rootNode=0,deleteNode=0;
void Solution();
void Input() {
int Nodes = 0, parentNodeInput = 0;
cin >> Nodes;
adj.resize(Nodes+1);
visited.resize(Nodes+1,false);
for (int i = 0; i < Nodes; i++) {
cin >> parentNodeInput;
//루트값이 아니고
if (parentNodeInput != -1) {
adj[i].push_back(parentNodeInput);
adj[parentNodeInput].push_back(i);
}
else rootNode = i;
}
//삭제할 노드값
cin >> deleteNode;
//root노드 삭제시 바로 답 출력
if (deleteNode == rootNode){
cout << 0;
return;
}
Solution();
}
//DFS방식으로
int SearchTree(int Node) {
int leafNodes = 0,childrenCnt=0;
//각 노드마다 방문 체크
visited[Node] = true;
//해당 노드에 연결된 노드들에 대해
for (int elem : adj[Node]) {
//방문 했다면 패스
if (visited[elem]) continue;
//해당 값이 지워진노드라면 패스
if (elem == deleteNode) continue;
//부모 제외하고 자식 몇개인지 체크용
childrenCnt++;
//위의 조건을 통과했다면 해당 값으로 재귀
leafNodes += SearchTree(elem);
}
//delete노드가 자식이라도 위에서 걸러짐. 따라서 자식 값이 0개면 리프노드이므로 1 리턴
if (childrenCnt==0) return 1;
//리프노드가 아니면 지금까지의 리프노드값 return
return leafNodes;
}
void Solution() {
cout<<SearchTree(rootNode);
}
int main() {
Input();
}문풀후생
루트 노드가 무조건 0이 아닐수도 있다는걸 생각을 못해서 헤맸다.
또한 자식 노드가 꼭 2개가 아니라 1개일수도 있다는건 캐치했지만
반대로 이진트리가 아니라 더 많을수도 있다는걸 생각을 못했다.
