문제
N개의 섬으로 이루어진 나라가 있습니다. 섬들은 1번 섬부터 N번 섬까지 있습니다.
1번 섬에는 구명보트만 있고 다른 섬에는 양들 또는 늑대들이 살고 있습니다.
늘어나는 늑대의 개체 수를 감당할 수 없던 양들은 구명보트를 타고 늑대가 없는 나라로 이주하기로 했습니다.
각 섬에서 1번 섬으로 가는 경로는 유일하며 i번 섬에는 pi번 섬으로 가는 다리가 있습니다.
양들은 1번 섬으로 가는 경로로 이동하며 늑대들은 원래 있는 섬에서 움직이지 않고 섬으로 들어온 양들을 잡아먹습니다. 늑대는 날렵하기 때문에 섬에 들어온 양을 항상 잡을 수 있습니다. 그리고 늑대 한 마리는 최대 한 마리의 양만 잡아먹습니다.
얼마나 많은 양이 1번 섬에 도달할 수 있을까요?
입력
첫 번째 줄에 섬의 개수 N (2 ≤ N ≤ 123,456) 이 주어집니다.
두 번째 줄부터 N-1개에 줄에 2번 섬부터 N번 섬까지 섬의 정보를 나타내는 ti, ai, pi (1 ≤ ai ≤ 109, 1 ≤ pi ≤ N) 가 주어집니다.
ti가 'W' 인 경우 i번 섬에 늑대가 ai마리가 살고 있음을, ti가 'S'인 경우 i번 섬에 양이 ai마리가 살고 있음을 의미합니다. pi는 i번째 섬에서 pi번 섬으로 갈 수 있는 다리가 있음을 의미합니다.
출력
첫 번째 줄에 구출할 수 있는 양의 수를 출력합니다.
예제 입력 1
4
S 100 3
W 50 1
S 10 1예제 출력 1
60예제 입력 2
7
S 100 1
S 100 1
W 100 1
S 1000 2
W 1000 2
S 900 6예제 출력 2
1200
문제풀이
해당 문제는 dfs로 풀 수 있다.
처음에 단순하게 리프 노드(노드=섬)들에서 시작해서 부모노드를 타고 올라가면서 양의 마릿수를 계산하는 코드를 작성했었다.
노드 개수가 많다보니 이러한 방법으로 했을 때 시간초과가 발생했다.
그래서 한 번 지나간 노드는 다시 지나가지 않는 방법으로 시간을 줄여야 했고, 이때 사용한 알고리즘이 바로 dfs이다.
로직은 다음과 같다.
1. 현재 노드에 자식노드가 있는 경우 자식노드를 방문한다.
2. 자식 노드가 없거나 자식 노드를 모두 방문한 경우, 해당 노드를 지나갈 수 있는 양 또는 남아있는 늑대의 마릿수를 계산한다.
3. 계산한 양 또는 늑대의 마릿수를 현재 노드의 부모 노드에 반영한다.
4. 1~3번 과정을 모든 노드를 방문할 때까지 반복한다.
한 가지 주의해야 할 점은, 각 노드의 양 또는 늑대의 마릿수의 범위가 10^9 이하이다 보니 합을 담을 변수를 long 타입으로 선언해야 한다.
작성코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
Node[] island = new Node[n + 1];
island[1] = new Node();
for (int i = 2; i < island.length; i++) {
st = new StringTokenizer(br.readLine());
if (island[i] == null)
island[i] = new Node();
if (st.nextToken().equals("W"))
island[i].wolf = Integer.parseInt(st.nextToken());
else
island[i].sheep = Integer.parseInt(st.nextToken());
int parent = Integer.parseInt(st.nextToken());
if (island[parent] == null)
island[parent] = new Node();
island[parent].children.add(i);
island[i].parent = parent;
}
// dfs 풀이
Stack<Integer> stack = new Stack<>();
stack.push(1);
while (stack.size() > 0) {
int cur = stack.peek();
if (island[cur].children.isEmpty()) {
cur = stack.pop();
if(cur == 1) break;
// 지금까지 계산한 것 부모 노드에 반영
if (island[cur].sheep > 0) {
// 지나갈 수 있는 양이 있는 경우
// 부모 노드에 지나갈 수 있는 양의 수 더하기
if(island[cur].sheep > island[island[cur].parent].wolf) {
island[island[cur].parent].sheep += island[cur].sheep - island[island[cur].parent].wolf;
island[island[cur].parent].wolf = 0;
}
// 지나갈 수 있는 양이 없는 경우
// 부모 노드에서 배부른 늑대의 수 빼기
else {
island[island[cur].parent].wolf -= island[cur].sheep;
}
}
}
else {
stack.push(island[cur].children.poll());
}
} // end of while
System.out.println(island[1].sheep);
} // end of main
} // end of class
class Node {
int parent;
Queue<Integer> children = new LinkedList<Integer>();
// int 범위 초과함
long sheep, wolf;
}
댓글