[백준] 16437번 : 양 구출 작전

16437번: 양 구출 작전

---

[DFS]

예시에 주어진 테스트 케이스 이외에 내가 만들어본 테스트 케이스이다. 이 예제가 DFS에서 조건처리해야 할 모든 것을 담고있다고 생각된다. 처음에 시간초과가 나게 풀었던 것은 모든 리프노드들에서 시작해 정점 1(Root)로 도착하며 그 때의 양이 몇마리 살아갔는지를 계산했었다. 하지만 그렇게 하면 이미 방문했었던 정점을 또 다시 방문하는 일이 발생한다. 그래서 시간초과를 받은 것 같다.

 

그래서 트리라는 것을 감안해 후위 순회(좌 - 우 - 중앙) 처럼 구현하였다. 위의 예제로 방문 순서를 보면, 루트에서 시작했을 때

5 -> 6 -> 3 -> 4 -> 2 -> 9 -> 8 -> 7 -> 0

순서가 될 것 같다.

 

그럼 이제 DFS를 살펴봐야 하는데 DFS는 인자 2개를 갖는다. 정점의 번호와 현재 양이 몇마리 인지에 대한 정보.

long DFS(int x, long sheep){}

예제를 가지고 흐름을 조금 살펴보자.

 

1.먼저 정점 5를 방문하면 300을 반환할 것이다. 곧이어 정점 6을 방문하는데 양 300마리를 데리고 정점 6을 방문했으니 양은 총 600마리가 있다.

 

2. 정점 3을 방문하는데 늑대가 500마리 있으니 양은 100마리만 남을 것이다.

 

3. 정점 4에는 양 500마리가 있으므로 현재 양은 총 600마리가 된다.

 

4. 정점 2에는 양 100마리가 있으므로 현재 양은 총 700마리가 된다. (여기서 700마리는 Root 정점에 머무른다.)

 

5. 정점 9에는 양 300마리가 있으므로 현재 양은 총 300마리 이다.

 

6. 정점 8에는 늑대 1000마리가 있으므로 현재 양은 -700마리 인데, 이는 불가능하므로 양은 0마리를 반환한다.

 

7 정점 7에는 양 700마리가 있으므로 현재 양은 700마리 이다.

 

8. 최종적으로 양쪽에서 받은 양 700 + 700마리 이므로 총 1400마리가 된다.

 

여기서 (6)이 중요하다. 양 -> 늑대 -> 양 부분에서 처음 양 -> 늑대 결과 값이 음수가 나오면 0을 반환해야한다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static long[] sheeps = new long[100];
    static List<Integer>[] list = new List[100];

    static long DFS(int x, long sheep){

        boolean isLeaf = true;

        long tmp = sheep;

        for(int next:list[x]){
            isLeaf = false;

            sheep += DFS(next, tmp);
        }

        if(isLeaf && sheeps[x] < 0) 
            return sheep;
        
        else if(sheep + sheeps[x] < 0) 
            return 0;
        
        else 
            return sheep + sheeps[x];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++)
            list[i] = new ArrayList<>();

        for(int i=2; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            char c = st.nextToken().charAt(0);
            int quantity = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());

            sheeps[i] = c == 'S'? quantity : -quantity;
            list[target].add(i);
        }

        System.out.println(DFS(1, 0));
    }
}
//Test cases
/*
* 7
S 300 1
W 500 2
S 600 3
S 300 3
S 700 1
W 1000 6
*
* 9
S 100 1
W 500 2
S 500 2
S 300 3
S 300 3
S 700 1
W 1000 7
S 300 8*/

# 시간 초과 Code </>

입력을 받으며 리프노드인 곳을 알아내 모든 리프노드에서 1번을 향해 DFS 시작. 탈출할 수 있는 양의 수를 취합한다. 아마 이는 방문했던 노드에 대해서도 다시 방문하는 지점이 존재하므로 시간초과가 난 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[] list;
    static long[][] arr;
    static boolean[] isLeaf;

    static void DFS(int x, long sheeps){

        if(x == 1) {
            arr[1][0] += sheeps;
            return;
        }

        sheeps += arr[x][0] - arr[x][1];
        arr[x][0] = 0;

        int next = list[x];

        if(sheeps < 0){
            arr[x][1] = -sheeps;
            DFS(next, 0);
        }
        else{
            arr[x][1] = 0;
            DFS(next, sheeps);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        isLeaf = new boolean[n+1];
        list = new int[n+1];
        arr = new long[n+1][2];

        Arrays.fill(isLeaf, true);

        for(int i=2; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            char c = st.nextToken().charAt(0);
            int quantity = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());

            //target 정점은 리프 노드가 아님
            isLeaf[target] = false;

            //해당 정점이 양인지 늑대인지 구분하여 마리 수 저장
            //양 : 0번째
            //늑대 : 1번째
            if(c == 'S') arr[i][0] = quantity;
            else         arr[i][1] = quantity;

            //인접 리스트 구성
            list[i] = target;
        }

        for(int i=2; i<=n; i++)
            if(isLeaf[i])
                DFS(i, 0);

        System.out.println(arr[1][0]);
    }
}