백준 25516번 거리가 k이하인 트리 노드에서 사과 수확하기 (JAVA)

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

25516번: 거리가 k이하인 트리 노드에서 사과 수확하기

 

저는 bfs를 통해 문제를 해결하였습니다.

평소 bfs에서는 방문 체크를 하지만, 트리이기 때문에 사이클이 존재하지 않아 방문 체크를 진행하지 않았습니다.

저는 time을 통해 해당 노드의 깊이를 확인하였고, time이 k를 넘어가면 탐색을 끝내도록 하여 문제를 해결하였습니다.

 

package BOJ.bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_25516 {
    private static final int EMPTY = 0;
    private static final int APPLE = 1;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int k = stoi.apply(st.nextToken());
        List<Integer>[] tree = new List[n];
        for(int i = 0 ; i < n ; i++){
            tree[i] = new ArrayList<>();
        }
        for(int i = 0 ; i < n-1 ; i++){
            st = new StringTokenizer(br.readLine());
            int parent = stoi.apply(st.nextToken());
            int child = stoi.apply(st.nextToken());
            tree[parent].add(child);
        }
        int[] apples = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n ; i++){
            apples[i] = stoi.apply(st.nextToken());
        }
        int result = bfs(tree,n,k,apples);
        System.out.println(result);
    }

    private static int bfs(List<Integer>[] tree, int n, int k, int[] apples) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        int time = 0;
        int cnt = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size ; s++){
                int now = q.poll();
                if(apples[now] == APPLE){
                    cnt++;
                }
                for(int next : tree[now]){
                    q.offer(next);
                }
            }
            time++;
            if(time > k){
                break;
            }
        }
        return cnt;
    }
}