백준 1068 - 트리

백준 1068 - 트리

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

★ 풀이

객체를 사용한 트리 문제는 처음 풀어보는 것 같다. 처음 했던 구상은 다음과 같다.

1. 주어진 정보를 토대로 트리를 구성한다.

2. DFS를 통해서 ROOT노드를 기점으로 탐색을 시작하는데, 탐색 중 삭제될 노드의 서브트리는 탐색하지 않는다. 리프 노드는 자식 노드가 하나도 없는 노드를 말하기 때문에 기저사례로 설정하고 발견한다면 return 1을 통해 세어준다.

중요한 것은 예외적인 상황도 고려해야 한다는 것이다.

왼쪽 트리는 논리 그대로 적용해도 맞는 정답이다. 하지만 오른쪽 트리는 논리 그대로 적용했다간 틀린 값을 얻을 수 밖에 없다. 왜냐면 자식 노드가 하나밖에 없는 상황에서 그 자식노드가 삭제될 노드라면 결국 자신이 리프 노드가 되어 return 1을 해주어야 하는데 그렇지 못하기 때문이다.

따라서 자식노드가 하나이고, 그 자식노드가 삭제될 노드라면 아래 조건을 만족할 것이기 때문에 이와 같은 경우 자신이 리프노드가 되어야 한다. 따라서 return 1을 해준다.

if(tree[node].children.size() == 1 && sum == 0) { return 1; }

★ 소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static Node[] tree; static int root, del; public static void main(String[] args) throws IOException { int n = Integer.parseInt(br.readLine()); tree = new Node[n]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i = 0; i children; public Node(int parent) { this.parent = parent; this.children = new ArrayList(); } }

from http://sweet-smell.tistory.com/142 by ccl(A) rewrite - 2021-12-07 14:00:38