[BOJ] 16437. 양 구출 작전

위상정렬 혹은 DFS를 사용할 수 있는 문제였다.

이 문제는 트리 문제로써 각 위치마다 양 또는 늑대가 존재하고, 루트까지의 양의 총합을 구하는 문제였다. 트리를 형성하고, 전체를 순회하는 구조이기에 맨처음 DFS로 접근해보았다. 1번(루트)에서 DFS를 한번도는 방식을 구상하였는데, 양의 수를 구하기 위해 DFS를 돌때 리턴값(양의 수)을 가지게 되고 최종적으로 자식노드 부터 리턴값을 보내어 1번(루트)에서 받아보는 방식을 생각해보았다.

package algostudy2;
 
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;
 
public class Main_bj_16437_양구출작전_2 {
    static int N;
 
    static boolean[] isSheep;        //양인지 늑대인지 체크
    static long[] animal;            //위치당 주어진 동물의 수
 
    static List<Integer>[] map;        //연결 그래프
    static Queue<Integer> queue;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
 
        isSheep = new boolean[N + 1];
        animal = new long[N + 1];
 
        map = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            map[i] = new ArrayList<>();
        }
        queue = new LinkedList<>();
 
        for (int i = 2; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            long num = Long.parseLong(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
 
            if (str.equals("S")) {
                isSheep[i] = true;
            }
 
            animal[i] = num;
            map[start].add(i);
        }
 
        System.out.println(dfs(1));
    }
 
    static long dfs(int i) {
        long curTotal = 0;
 
        for (int next : map[i]) {
            curTotal += dfs(next);
        }
 
        if (i == 1) {
            return curTotal;
        }
 
        if (isSheep[i]) {
            curTotal += animal[i];
        } else {
            curTotal -= animal[i];
            if (curTotal < 0) {
                curTotal = 0;
            }
        }
 
        return curTotal;
    }
 
}
 

 

DFS방법외에도 트리이기때문에 사이클이 없는것이 보장되는 상황에서 위상정렬을 사용해보았다. 

package algostudy2;
 
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;
 
public class Main_bj_16437_양구출작전 {
    static int N;
 
    static boolean[] isSheep;        //양인지 늑대인지 체크
    static long[] animal;            //위치당 주어진 동물의 수
    static long[] totalAnimal;        //위치당 계산된 동물의 수
 
    static List<Integer>[] map;        //연결 그래프
    static int[] indegree;
    static Queue<Integer> queue;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
 
        isSheep = new boolean[N + 1];
        animal = new long[N + 1];
        totalAnimal = new long[N + 1];
 
        map = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            map[i] = new ArrayList<>();
        }
        indegree = new int[N + 1];
        queue = new LinkedList<>();
 
        for (int i = 2; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            long num = Long.parseLong(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
 
            if (str.equals("S")) {
                isSheep[i] = true;
            }
 
            animal[i] = num;
            map[i].add(end);
            indegree[end]++;
        }
 
        topological();
 
        System.out.println(totalAnimal[1]);
    }
 
    static void topological() {
        for (int i = 2; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
 
        while (!queue.isEmpty()) {
            int cur = queue.poll();
 
            if (cur == 1) {
                return;
            } else {
                if (isSheep[cur]) {
                    totalAnimal[cur] += animal[cur];
                } else {
                    totalAnimal[cur] -= animal[cur];
                    if (totalAnimal[cur] < 0) {
                        totalAnimal[cur] = 0;
                    }
                }
            }
 
            for (int next : map[cur]) {
                indegree[next]--;
 
                totalAnimal[next] += totalAnimal[cur];
 
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
 
            }
        }
    }
}