백준 1068 트리 Java

https://www.acmicpc.net/problem/1068

1068번: 트리

 

풀이

1. 이중 리스트에 자식 노드 넣기

2. 루트 노드에서 시작해 리프 노드 세기

3. DFS 순회하며 다음 순회할 노드가 잘린 노드면 건너뛰기

 

코드

public class Pro1068 {
	static List<List<Integer>> a = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n, c ,del,root = 0;
		
		StringTokenizer st = new StringTokenizer(bf.readLine());
		n = Integer.parseInt(st.nextToken());
		for(int i=0;i<n;i++) {
			a.add(new ArrayList<>());
		}
		st = new StringTokenizer(bf.readLine());
		for(int i=0;i<n;i++) {
			int tmp = Integer.parseInt(st.nextToken());
			if(tmp == -1)root = i;
			if(tmp != -1)a.get(tmp).add(i);
		}
		st = new StringTokenizer(bf.readLine());
		del = Integer.parseInt(st.nextToken());
	
		if(del == root)System.out.println(0);
		else System.out.println(dfs(root, del));
	}
	static int dfs(int here, int del) {
		int ret = 0;
		int child = 0;
		for(int there : a.get(here)) {
			if(there == del)continue;
			ret += dfs(there, del);
			child ++;
		}
		if(child==0)return 1;
		else return ret;

	}
}