[백준] 1068 - 트리

[문제링크]

1068번: 트리

 

0. treeNode 자료구조는 부모 index, 자기 value, 자식 index의 List로 구성됨

  - treeNode의 배열로서 tree를 표현한다

 

1. 문제의 입력은 0-base지만, 편의상 1-base로 변경. 0은 가상의 head node로서 사용한다

 

2. 입력을 받으며 자신의 parent에 등록 + parent의 child에 등록해 tree 완성

 

3. 0번을 parent로 가지는, tree의 root노드로부터 bfs 탐색한다

  - child가 없는 node는 leaf이므로 센다

 

4. 탐색 노드가 삭제할 node일 경우, 해당 노드로부턴 더 이상 탐색하지 않는다

  - 삭제 node의 parent의 child 갯수가 1개라면 : 이 node의 삭제로 parent노드가 leaf가 되었으니 센다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int root=0, deadNode=0, cntLeaf=0;
		int N = pint(br.readLine());
		treeNode[]tree = new treeNode[N+1];
		for (int i = 0; i <= N; i++) {
			tree[i]=new treeNode();
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			int p = pint(st.nextToken())+1;
			tree[i].parents=p;
			tree[i].value=i;
			tree[p].children.add(i);
			if(p==0)root=i;
		}
		deadNode=pint(br.readLine())+1;
		
		Queue<Integer>qu = new LinkedList<>();
		qu.offer(root);
		cntLeaf=0;
		while(!qu.isEmpty()) {
			int node=qu.poll();
			if(tree[node].value==deadNode) {
				if(tree[node].parents!=0 && tree[ tree[node].parents ].children.size()==1) {
					cntLeaf++;
				}
				continue;
			}
			
			if(tree[node].children.isEmpty()) {
				cntLeaf++;
			}
			else {
				for (int i = 0; i < tree[node].children.size(); i++) {
					int next=tree[node].children.get(i);
					qu.offer(next);
				}
			}
		}
		System.out.println(cntLeaf);
	}
	static class treeNode{
		int parents;
		int value;
		ArrayList<Integer>children=new ArrayList<>();
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면