백준 1068

문제 

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

알고리즘

1. bfs

풀이

1. 트리 구조 생성

각 노드에 대해 빈 리스트를 생성합니다.  부모가 -1인 경우는 루트 노드로 처리하고, -1이 아니면 해당 부모의 자식 리스트에 현재 노드 번호를 추가합니다.

2. 삭제할 노드 처리

삭제할 노드를 선택하면 그 노드와 그 아래의 모든 노드들은 트리에서 제거되어야 합니다.

단순히 DFS로 방문하면서 삭제할 노드를 만나면 무시하게 되면, 부모 노드의 자식 리스트에는 여전히 삭제된 노드 번호가 남게 됩니다. 부모 노드가 자식 리스트에 삭제된 노드를 가지고 있다면, 실제로는 삭제되었지만 리스트가 비어있지 않아 리프 노드가 아니라고 잘못 판단할 수 있습니다.

3. 트리 탐색

BFS활용해 남은 트리를 탐색합니다.

삭제할 노드가 루트인 경우, 전체 트리가 삭제되므로 결과는 0입니다.

탐색 도중 자식 노드를 추가할 때, 삭제할 노드와 같은 번호의 노드는 건너뜁니다.

탐색한 노드에서 자식 리스트를 확인할 때, 자식이 하나도 없다면 해당 노드는 리프 노드로 간주합니다.

코드

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int N = Integer.parseInt(br.readLine());
			List<Set<Integer>> graph = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				graph.add(new HashSet<>());
			}
			String[] s = br.readLine().split(" ");
			int root = 0;
			for (int i = 0; i < s.length; i++) {
				int i1 = Integer.parseInt(s[i]);
				if (i1 == -1) {
					root = i;
					continue;
				}
				graph.get(i1).add(i);
			}
			int a = Integer.parseInt(br.readLine());
			Deque<Integer> dq = new ArrayDeque<>();
			if (root != a) {
				dq.add(root);
			}
			int count = 0;
			while (!dq.isEmpty()) {
				Integer poll = dq.poll();
				Set<Integer> integers = graph.get(poll);
				integers.remove(a);
				if (integers.isEmpty()) {
					count++;
					continue;
				}
				dq.addAll(integers);
			}
			System.out.println(count);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}