글 읽기 - 1068문제 틀린케이스가 뭔지 모르겠습니다

leeho203 7년 전 0

parent배열을 이용해서 리프노드의 갯수를 구하는 재귀함수형태로 답안을 작성했습니다.

각 트리의 노드가 3개 이상인 경우, 부모노드의 부모노드를 자르는 경우 등등 테스트해봤지만 틀린케이스가 뭔지 모르겠습니다

제 머리로는 케이스가 생각이 안나서 고수님들에게 여쭤봅니다 ㅠㅠ 도와주세요!!

import java.util.*;

public class Main {
	private static final int INF = 987654321;
	static int n;
	static int[] parent;

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		parent = new int[n];
		int root = -1;
		for (int i = 0; i < n; i++) {
			int p = sc.nextInt();
			parent[i] = p;
			// 루트 노드 저장
			if (p == -1)
				root = i;
		}

		// 노드 끊기
		parent[sc.nextInt()] = INF;
		System.out.println(findLeafNode(root));
	}

	// 리프 노드의 갯수를 리턴
	static int findLeafNode(int root) {
		int result = 0;
		boolean hasDescendants = false;

		// 자손을 모두 찾아서 자손들의 리프노드의 갯수를 result에 누적
		for (int next = 0; next < n; next++) {
			if (next == root)
				continue;
			// 자식노드가 있는 경우
			if (root == parent[next]) {
				result += findLeafNode(next);
				hasDescendants = true;
			}
		}

		// 자손이 있는 경우 result 반환, 자손이 없는 경우 1 반환
		return (hasDescendants) ? result : 1;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1068문제 틀린케이스가 뭔지 모르겠습니다

leeho203 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말