[백준] 알고리즘 분류(트리,JAVA)16437번, 양 구출 작전

문제 링크

16437번: 양 구출 작전

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 각 섬에는 1번 섬으로 가는 유일한 경로가 존재합니다.

2. 늑대는 섬에 들어오는 양을 잡아먹으며 최대 1회만 먹습니다.

3. 모든 양이 1번섬으로 출발할 때 도착하는 마리를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 후위 탐색을 통해 양의 이동을 진행합니다.

 

3. 1번 섬에 도착한 양의 마릿수를 결과로 출력합니다.

 

 

양의 이동(후위 탐색)

후위 탐색

 

Left ▶ Right ▶ Root

※Left와 Right가 중요한 것이 아닌 마지막에 Root를 탐색한다는 것을 이용하기 위해서 후위 탐색을 사용!

 

이 문제에서 트리의 Root노드는 항상 1번 노드

 

후위 탐색을 진행하여 양의 이동을 진행하면 마지막에는 1번섬에 도착하게됩니다.

 

후위 탐색을 종료하면 1번 섬에 도착한 양의 마릿수를 구할 수 있습니다.

 

예제입력 진행되는 과정을 살펴보시면 이해가 되실 것입니다!

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 4

 

트리 정보

2번 섬 =  양 : 100마리

3번 섬 = 늑대 : 50마리

4번 섬 = 양 : 10마리

2. 후위 탐색을 통해 양의 이동을 진행합니다.

 

양의 이동 시작!(후위 탐색 시작!)

2번 섬에는 양이 100마리 존재하기 때문에 3번 섬으로 100마리가 이동합니다.

4번 섬에는 양이 10마리 존재하기 때문에 1번 섬으로 10마리가 이동합니다.

3번 섬에는 양이 100마리와 늑대 50마리가 존재하기 때문에 1번 섬으로 50(100-50)마리가 이동합니다.

 

※만약 양의 수보다 늑대수가 많으면 양이 다 잡아먹히고 양은 이동하지 않습니다!

 

3. 1번 섬에 도착한 양의 마릿수를 결과로 출력합니다.

 

2번 섬(양 100마리) ▶ 3번 섬(양 100마리, 늑대 50마리) ▶ 1번 섬(양 50마리)

 

4번 섬(양 10마리) ▶ 1번 섬(양 10마리)

 

1번 섬에 도착한 양 : 50 + 10 = 60

 

60을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 각 섬의 정보를 띄어쓰기 기준 나누었습니다.
• search함수를 실행하여 후위 탐색으로 모든 양이 1번 섬으로 이동을 진행합니다.
• 후위 탐색이 종료되었을 때 1번 섬에 도착한 양의 마릿수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 후위탐색(DFS)로 모든 양이 1번 섬으로 이동하는 것을 탐색합니다.

 

결과코드

 

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

class Main {
    //섬에 정보 관련 클래스
    static class info{
        long value;	//마릿수
        boolean kinds;	//true : 양, false : 늑대
        public info(long value, boolean kinds) {
            this.kinds = kinds;
            this.value = value;
        }
    }
    //트리 정점 연결하는 간선 정보
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    static info[] infos;	//각 섬에 정보 저장 배열
    public static void main(String args[]) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        infos = new info[N+1];
        for(int i=0;i<=N;i++)
            tree.add(new ArrayList<>());
        StringTokenizer st;
        //각 섬의 정보 및 트리 간선 수립!
        infos[1] = new info(0, true);
        for(int i=2;i<=N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            char t = st.nextToken().charAt(0);
            long a = Long.parseLong(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            tree.get(p).add(i);
            infos[i] = new info(a, t == 'S');
        }
        //후위탐색으로 얻은 1번섬의 양의 마릿수 BufferedWriter 저장
        bw.write(search(1) + "");
        bw.flush();
        bw.close();
        br.close();
    }
    //후위 탐색(DFS)으로 각 섬에서 양들이 1번섬으로 오는 과정 탐색
    static long search(int index) {
        long sum = 0;	//현재 양의 마릿수
        //Left, Right 정점 탐색!
        for(int next : tree.get(index)){
            sum += search(next);
        }
        //Root 정점 탐색
        if(infos[index].kinds)	//현재 섬이 양일 때
            return sum + infos[index].value;	//양의 마릿수 그대로 이동!
        else	//현재 섬이 늑대일 때
            return (sum - infos[index].value < 0) ? 0 : sum-infos[index].value;
            //늑대가 현재까지 이동한 양보다 많으면 양은 0마리 이동!
            //늑대가 현재까지 이동한 양보다 적으면 (양 - 늑대)마리 이동! 
    }
}