[2020여름] 모각코 4회차 활동

악 너무 어렵다.

 

백준 알고리즘 1068번

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

1068번: 트리

1068번

트리에서 리프노드의 수를 세는 문제이다.

처음 입력에는 노드의 개수가 나오고 두번째는 부모의 노드를 알려주는 배열이 입력된다. 마지막에 입력되는 수의 노드를 삭제한 후에 리프노드의 수를 세어야 한다.

 

너무 어려웠다!

 

해결방법

입력받은 부모의 노드를 알려주는 배열과 노드의 자식 수를 저장할 int형 이차원 배열을 만들었다.

node[][0]에서는 부모의 노드를 알려주고 node[][1]에서는 자식의 수를 알려준다.

 

Erase() 함수

삭제할 노드 = erase

erase의 부모가 루트가 아닐 때만 그 부모의 자식 수를 -1 해준다.

erase는 이제 삭제했으니까 node[erase][0]을 -99로 지운 노드라고 알려준다.

자식이 있다면

node[][0]을 살펴보면서(부모 노드를 보면서) erase와 같으면 Erase()를 호출하면서 재귀로 삭제해준다.

 

count() 함수

node[][0]이 -99아니고 node[][1]이 0이면 카운트

= 부모가 지워지지않았고 자식이 없으면 카운트

 

코드

import java.util.Scanner;
import java.util.Stack;

public class Main {
	static int nodeNum;
	static int[][] node;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String[] input = new String[3];
		for (int i = 0; i < 3; i++) {
			input[i] = sc.nextLine();
		}

		nodeNum = Integer.parseInt(input[0]);

		node = new int[nodeNum][2];

		String[] strArr = input[1].split(" ");

		for (int i = 0; i < strArr.length; i++) {
			node[i][0] = Integer.parseInt(strArr[i]);
			if (node[i][0] != -1) {
				node[node[i][0]][1]++;

			}
		}

		int erase = Integer.parseInt(input[2]);
		Erase(erase);

		System.out.println(count(node));
	}

	public static void Erase(int erase) {
		if (node[erase][0] != -1) {
			node[node[erase][0]][1]--;

		}
		node[erase][0] = -99;
		if (node[erase][1] > 0) { 
			for (int i = 0; i < nodeNum; i++) {
				if (node[i][0] == erase) {
					Erase(i);
				}
			}
		}
	}

	public static int count(int[][] node) {
		int result = 0;
		for (int i = 0; i < node.length; i++) {
			if (node[i][0] != -99 && node[i][1] == 0) {
				result++;
			}
		}
		return result;
	}
}

 

ㅎㅎ 0노드일 경우로만 코드 짜놔서 안되가지고 왜 안되지!!!!!!!!!!!!이러고 있었다. 며칠동안 ㅠㅠ

바보ㅜㅜ