백준 16437번 양 구출 작전 (JAVA)

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

16437번: 양 구출 작전

 

저는 해당 문제를 DFS를 이용해 문제를 해결하였습니다.

처음에는 BFS를 통해 문제를 해결하려 하였지만, 시간초과를 피할 수 없었습니다. 각각의 양에서 경로를 이동하는 로직이였는데 이럴 경우 중복되는 노드를 여러번 방문할 수 있어 시간초과가 나오는 것 같습니다.

그래서 dfs를 통해 문제를 해결하였습니다. dfs를 사용하면 한 노드에 한 번만 방문해서 문제를 해결할 수 있었습니다.

각 노드를 방문하고 해당 노드가 늑대라면 하위 노드들을 방문하여 양의 개수를 구하고 이 값이 늑대보다 크다면 그 갭을 리턴하고 아니라면 0을 리턴하였습니다. 양이라면 하위 노드들의 양과 현재 양들의 값을 합쳐서 리턴하였습니다.

 

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_16437_2 {
    private static class Node{
        int number;
        long cnt;

        public Node(int number, long cnt) {
            this.number = number;
            this.cnt = cnt;
        }
    }
    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[] weight = new int[n+1];
        List<Integer>[] list = new List[n+1];
        for(int i = 0 ; i <= n ; i++){
            list[i] = new ArrayList<>();
        }
        for(int i = 2 ; i <= n ; i++){
            st = new StringTokenizer(br.readLine()," ");
            char type = st.nextToken().charAt(0);
            int cnt  = stoi.apply(st.nextToken());
            int parent  = stoi.apply(st.nextToken());
            list[parent].add(i);
            if(type == 'S'){
                weight[i] = cnt;
            }else {
                weight[i] = -cnt;
            }
        }
        long result = dfs(1,weight,list);
        System.out.println(result);
    }

    private static long dfs(int now, int[] weight, List<Integer>[] list) {
        long result = 0;
//        System.out.println(now);
        for(int next : list[now]){
            result += dfs(next,weight,list);
        }
        if(weight[now] >= 0){
            return result + weight[now];
        }
        if(weight[now] < 0 && result + weight[now] > 0){
            return result +weight[now];
        }
        return 0;
    }

    private static long bfs(int[] wolf, Queue<Node> q, int n, int[] path) {
        long result = 0;
        while(!q.isEmpty()){
            Node now = q.poll();
//            System.out.println(now.number +" "+now.cnt);
            if(now.number == 1){
                result += now.cnt;
                continue;
            }
            long min = Math.min(now.cnt,wolf[now.number]);
            long cnt = now.cnt - min;
            wolf[now.number] -= min;
            if(cnt > 0){
                q.offer(new Node(path[now.number],cnt));
            }
        }
        return result;
    }
}