백준 양 구출 작전(16437)
1. 힌트
1) "각 섬에서 1번 섬으로 가는 경로는 유일", 섬들은 트리의 조건을 만족한다.
2) 모든 양이 살고 있는 섬에 대해서 루트까지 이동시키는 방법으로는 시간 초과를 피할 수 없다.
3) 트리의 재귀적인 성질을 이용하면 어떤 정점에 도착할 수 있는 양의 수를 구하고, 재귀적으로 나타낼 수 있다.
2. 접근
1) 문제를 분해할 수 있을까?
문제에서 "각 섬에서 1번 섬으로 가는 경로는 유일"하다고 했는데 어떻게 이 개의 섬들이 트리임을 알 수 있을까?
트리는 모든 정점간의 경로가 유일한 그래프이다. 각 섬은 1번 섬으로 가는 경로가 존재하므로 1번 섬을 경유점으로 생각하면 모든 섬 간의 경로는 유일할 수 밖에 없다.
트리이기 때문에 어떤 임의의 정점을 잡고 루트라고 하여도 전혀 무리가 없다, 그렇기 때문에 우리는 1번 정점을 루트라고 하고, 모든 양들이 사는 섬에서 부모로 올라가는 간선을 따라 이동시켜볼 수 있다.
하지만 트리가 연결 리스트에 가깝게 이러한 모양으로 존재할 수도 있다. 이렇게 되면 모든 양을 이동시키는 시간 복잡도는 이다.
그렇다면 트리의 순회를 이용해서 한 정점은 한 번만 방문하게 하는 방법으로 풀 수 있도록 문제를 정의하여 보자
번 정점에 도착할 수 있는 양의 수
이렇게 정의하면 이 우리가 구하고자 하는 값이 된다. 의 값을 구하기 위해서는 번 정점의 모든 자식들에 대해서 값을 알아야 하는데 이는 트리의 중위 순회로 구현하면 모든 정점에 대해 한 번만 방분하여 의 시간 복잡도로 해결 가능하다.
3. 구현
public class Main {
static int[] parent;
static ArrayList<ArrayList<Integer>> children;
static int[] amount;
// here을 루트로 하는 서브트리에서 루트에 도착하고 살아남는 양의 수
static long inorder(int here) {
long sum = amount[here];
for (int ch : children.get(here)) sum += inorder(ch);
return Math.max(sum, 0);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
parent = new int[N + 1]; parent[1] = 1;
children = new ArrayList<>(N + 1);
for (int i = 0; i < N + 1; i++) children.add(new ArrayList<>());
amount = new int[N + 1];
for (int i = 2; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
String t = st.nextToken();
amount[i] = Integer.parseInt(st.nextToken());
if (t.equals("W")) amount[i] *= -1;
int p = Integer.parseInt(st.nextToken());
parent[i] = p;
children.get(p).add(i);
}
System.out.println(inorder(1));
}
}
1) 시간 복잡도
함수가 모든 정점에 대해서 한 번씩만 호출된다는 것은 명확하다. 하지만 자식들을 순회할 때 시간 복잡도는 어떻게 되는 것일까?
함수를 얼마나 호출하던 간에 자식들에 대해서 순회하는 횟수는 트리에 존재하는 간선의 개수와 동일하다. 트리의 정점이 개 이면 간선은 개 이므로 시간 복잡도는 이 된다.
2) 테스트 케이스
Author And Source
이 문제에 관하여(백준 양 구출 작전(16437)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@axiom0510/b16437저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)