알고리즘 문제풀이/백준
[백준 1068] 트리(JAVA)
소보루:-)
2020. 3. 14. 23:09
https://www.acmicpc.net/problem/1068
1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
www.acmicpc.net
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int N;
static int[][] nodes;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
N=sc.nextInt();
nodes=new int[N][2];//0부모노드 1자식수
for(int i=0; i<N; i++) {
nodes[i][0]=sc.nextInt();
}
getChildNum();
remove(sc.nextInt());
System.out.println(getAnswer());
}
private static int getAnswer() {
int cnt=0;
for(int i=0; i<N; i++) {
if(nodes[i][0]!=-2 &&nodes[i][1]==0) {
cnt++;
}
}
return cnt;
}
private static void remove(int num) {
if(nodes[num][0]!=-1) {//루트노드아니면
nodes[nodes[num][0]][1]--;//부모노드의 자식수 줄이기
}
nodes[num][0]=-2;//지워진 노드 표시
if(nodes[num][1]>0) {//자식이 있으면
for(int i=0; i<N; i++) {
if(nodes[i][0]==num) {
remove(i);
}
}
}
}
private static void getChildNum() {
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(nodes[j][0]==i) nodes[i][1]++;
}
}
}
}