[백준/java] 1068. 트리

문제 링크 - https://www.acmicpc.net/problem/1068

🌱 문제

🌱 풀이

• 리스트배열 자료형을 이용하여 각 노드번호의 배열에 자식 노드 번호들을 리스트로 담아 주었다.
• 그리고 삭제되는 노드부터 아래방향으로 돌면서(트리기준) 자식들을 타고타고 내려가면서 자식들을 삭제해주었다.
• 삭제 과정은 cnt[]배열을 통해 삭제된 배열은 cnt[i]=-1 로 처리하고 i의 부모의 cnt값을 1감소 시켰다.
• 여러번 틀린 후에 겨우 맞출 수 있었다.

틀렸던 이유 1

• 예제 답은 잘 나왔는데 백준 채점을 돌리면 계속 NullPointerException 이어서 그 이유를 찾아보았다.
• 아래 코드에서 주석처리한 부분과 같이 처음에는 ArrayList배열 초기화를 미리 안하고, for문안에서 했다. 하지만 list[x].add(i); 부분에서 NullPointerException이 날 수 있기 때문에 초반에 초기화를 하도록 변경했다.

	for (int i = 0; i < n; i++) {
//			list[i] = new ArrayList<Integer>(); // 6번째아래에 list[x].add(i) 코드가 있기 때문에 list[]를 미리 초기화 안하면 NullPointerError발생한다 
			int x = Integer.parseInt(st.nextToken()); //x: i번째 노드의 부모 인덱스 
			parent[i] = x; // 부모 노드 인덱스 저장 
			if (x == -1)
				continue;
			cnt[x]++; // 자식 수 증가 
			list[x].add(i);
		}

틀렸던 이유 2

• 75%정도에서 틀렸었는데, 그 이유는 아래와 같은 반례를 생각하지 못했었다.
• 나는 처음에는 루트노드가 리프노트가 되는 경우를 생각 못해서 parent[]배열을 이용해서 부모 노드의 인덱스를 저장하는 과정은 안했다.
• 하지만, 아래의 반례를 보면 루트노드의 자식이 제거되어서 리프노트가 되는 경우를 고려해야한다.
• 그래서 처음에 부모정보를 입력받을때 parent[]배열에 각각의 부모가 누구인지 저장해준 후, 재귀 함수에서 삭제되는 노드의 부모의 자식 수를 줄이는 과정을 추가해주었다. -> 이렇게 하여 루트노드가 리프노드가 되는 경우 고려 가능하게됨.

# 반례
2
-1 0
1
정답:1, 내가 나왔던 값 : 0

🌱 코드

package Dec_week01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 1068. 트리 
public class boj_1068 {
	static int n;
	static int cnt[]; // 자식의 수
	static int parent[]; // 부모가 몇번 노드인지 저장
	static ArrayList<Integer> list[]; // arraylist에 자식들 노드 번호 저장 
	static int target; // 삭제하는 노드 번호 
	static int answer; // 리프 노드의 갯수

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		cnt = new int[n];
		parent = new int[n];

		list = new ArrayList[n]; 
		for (int i = 0; i < n; i++) { // 리스트배열 초기화 
			list[i] = new ArrayList<Integer>();
		}

		st = new StringTokenizer(br.readLine());
		target = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
//			list[i] = new ArrayList<Integer>(); // 6번째아래에 list[x].add(i) 코드가 있기 때문에 list[]를 미리 초기화 안하면 NullPointerError발생한다 
			int x = Integer.parseInt(st.nextToken()); //x: i번째 노드의 부모 인덱스 
			parent[i] = x; // 부모 노드 인덱스 저장 
			if (x == -1)
				continue;
			cnt[x]++; // 자식 수 증가 
			list[x].add(i);
		}
		if (parent[target] == -1) { // 삭제하는 노드가 루트노드인경우 0출력하고 종료 
			answer = 0;
			System.out.println(answer);
			return;
		}

		func(target);
		for (int i = 0; i < n; i++) {
//			System.out.println(i + "의 cnt: " + cnt[i]); 
			if (cnt[i] == 0)
				answer++;
		}
		System.out.println(answer);

	}

	public static void func(int x) {
		cnt[x] = -1; // 삭제된 노드 처리 
		cnt[parent[x]]--; // 삭제된 노드의 부모의 자식수 1 감소 
		for (int i = 0; i < list[x].size(); i++) {
			int next = list[x].get(i);
			func(next); // 자식 타고 내려가면서 재귀 반복 
		}
	}

}