글 읽기 - 어느 부분이 문제일까요?

gkdud583 2년 전 0

각 노드의 자식노드의 수를 구하고 자식노드의 수가 D이상일경우 ans를 증가시키는식으로 구했습니다.

게시판에 있는 케이스는 모두 맞게 나옵니다.ㅠ

import java.io.*;
import java.util.*;



class Main{ 
    static ArrayList<Integer> edge[];
    static int ans = 0;
    public static void main(String[]args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input[] = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int S = Integer.parseInt(input[1]);
        int D = Integer.parseInt(input[2]);

        edge = new ArrayList[N+1];
        for(int i=1; i<=N; i++)
            edge[i] = new ArrayList<>();
        
        for(int i=0; i<N-1; i++){
            input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            edge[a].add(b);
            edge[b].add(a);
        }

        solve(N, S, D);
        System.out.println(ans * 2);

    }
    static void solve(int N, int S, int D){
        boolean check[] = new boolean[N+1];
        boolean ansCheck[] = new boolean[N+1];
        check[S] = true;
        dfs(S, S, D, check, ansCheck);
    }
    static int dfs(int i, int S, int D, boolean check[], boolean ansCheck[]){
        int childCnt = 0;
        boolean isLeafNode = true;
        for(int j=0; j<edge[i].size(); j++){
            int nxt = edge[i].get(j);

            if(check[nxt])
                continue;
            check[nxt] = true;
            isLeafNode = false;
            int ret = dfs(nxt, S, D, check, ansCheck) + 1;
            childCnt += ret;
            if(i != S && ret >= D){
                if(!ansCheck[i]){//서브트리가 2개 이상일때 현재 노드를 중복으로 더하지 않기 위함
                    // System.out.println("선택: "+i);
                    ansCheck[i] = true; 
                    ans++;
                }
            }

        }
        if(isLeafNode){ 
            /*
            2 1 0
            1 2
            같은 테스트케이스 위함
            */
            if(i != S && D == 0 && !ansCheck[i]){
                ansCheck[i] = true;
                ans++;
            }

        }
        return childCnt;
    }
}

gkdud583 2년 전 0

자문자답입니다.

문제를 잘못 이해했습니다.

틀린 부분을 찾는데 사용한 반례입니다.

17 1 4
1 2
2 3
3 5
5 9
5 10
3 6
6 11
6 12
2 4
4 7
7 13
7 14
4 8
8 15
8 16
1 17

정답: 0

출력: 2

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

문제

문제

출처

ICPC

어느 부분이 문제일까요?

gkdud583 2년 전 0

gkdud583 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말