Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- springboot
- java의 정석
- DxTrace
- 클린코드
- 2166번
- 10830번
- 백준
- 코딩 테스트
- 2156번
- Design Patterns
- 17장
- 1043번
- java
- 가장 긴 증가하는 부분 수열2
- BOJ
- SerialDate 리펙터링
- Adapater Pattern
- 11758번
- programmers
- 1300번
- Design Pattern
- Spring
- 코딩테스트
- Dxerr.h
- 자바의 정석
- 9장
- 냄새와 휴리스틱
- 2206번
- 11286번
- 프로그래머스
Archives
- Today
- Total
Don't give up!
[백준] 1068번 : 트리 (java) 본문
어떻게 생각하고 문제를 풀었는가?
주어진 입력이 i번째 노드의 부모 노드가 몇번째 노드인지 나타내고 있고, 0번째 노드가 루트 노드가 아닐 수 있다는 점, 자식 노드의 수가 정해져 있지 않다는 점을 고려하였습니다.
이를 해결하고자 N개의 노드가 가리키는 부모 노드의 인덱스를 노드 초기화시 저장하고, 모든 노드가 초기화된 후 각 노드가 가리키는 부모 노드의 자식 노드를 추가하도록 하였습니다.
노드의 삭제시 자식 노드에서 해당 노드를 삭제, 리프 노드 계산은 루트 노드에서 시작하여 자식 노드를 dfs로 탐색하도록 하여 문제를 해결할 수 있다고 생각하였습니다.
코드
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
class Main {
static int N, target, root;
static Node[] tree;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(reader.readLine());
tree = new Node[N];
StringTokenizer parentTokenizer = new StringTokenizer(reader.readLine());
for(int i=0; i<N; i++){
int parent = Integer.parseInt(parentTokenizer.nextToken());
tree[i] = new Node(parent);
if(parent<0) root = i;
}
target = Integer.parseInt(reader.readLine());
reader.close();
for(int i=0; i<N; i++){
if(!tree[i].isRoot()){
int parent = tree[i].parent;
tree[parent].addChild(i);
}
}
if(target == root){
System.out.println(0);
}else{
int parent = tree[target].parent;
tree[parent].removeChild(target);
int leafSize = getLeafSize(root);
System.out.println(leafSize);
}
}
static int getLeafSize(int index){
if(tree[index].isLeaf()) return 1;
int sum = 0;
for(int i=0; i<tree[index].getChildrenSize(); i++){
sum += getLeafSize(tree[index].children.get(i));
}
return sum;
}
}
class Node{
int parent;
List<Integer> children;
public Node(int parent){
this.parent = parent;
this.children = new ArrayList<>();
}
public void addChild(int child){
this.children.add(child);
}
public void removeChild(int child){
this.children.remove(Integer.valueOf(child));
}
public boolean isLeaf(){
return this.children.isEmpty();
}
public int getChildrenSize(){
return this.children.size();
}
public boolean isRoot(){
return this.parent < 0;
}
}
Node 클래스를 선언, Node 배열 N개를 초기화하여 i번째 노드에 접근할 수 있습니다.
부모 노드의 인덱스, 자식 노드들의 인덱스를 저장한 후, 배열로부터 이를 찾아 자식노드를 추가하고 리프 노드인지 확인할 수 있습니다.
삭제하려는 노드가 루트 노드라면 모든 노드가 삭제되었으므로 0을 리턴, 루트 노드가 아니라면 해당 노드의 부모 노드로에게 자식 리스트에서 제거하도록 하고, 루트 노드로부터 dfs를 수행합니다.
'Coding Test > BOJ' 카테고리의 다른 글
[백준] 1022번 : 소용돌이 예쁘게 출력하기 (java) (0) | 2021.08.07 |
---|---|
[백준] 1051번 : 숫자 정사각형 (java) (0) | 2021.07.19 |
[백준] 1089번 : 스타트링크 타워 (0) | 2021.07.18 |