백준 16437: 양 구출 작전

문제 요약

N개의 섬으로 이루어진 나라가 있습니다. 섬들은 1번 섬부터 N번 섬까지 있습니다.

1번 섬에는 구명보트만 있고 다른 섬에는 양들 또는 늑대들이 살고 있습니다.

늘어나는 늑대의 개체 수를 감당할 수 없던 양들은 구명보트를 타고 늑대가 없는 나라로 이주하기로 했습니다.

각 섬에서 1번 섬으로 가는 경로는 유일하며 i번 섬에는 pi번 섬으로 가는 다리가 있습니다.

양들은 1번 섬으로 가는 경로로 이동하며 늑대들은 원래 있는 섬에서 움직이지 않고 섬으로 들어온 양들을 잡아먹습니다. 늑대는 날렵하기 때문에 섬에 들어온 양을 항상 잡을 수 있습니다. 그리고 늑대 한 마리는 최대 한 마리의 양만 잡아먹습니다.

얼마나 많은 양이 1번 섬에 도달할 수 있을까요?

문제 분류

• 그래프 이론
• 그래프 탐색
• 트리
• DFS

문제 풀이

루트노드를 1로 보고, 1에서부터 DFS탐색하면 된다. 결국 어떤 노드를 탐색할때, 해당 노드는 지금까지 살아남아온 양의 수만 반환하면 되고, 루트노드는 해당 값들을 모두 누적하여 반환하면 된다.

백준 사이트의 예제 그림을 예로, 처음에 DFS(1)을 한다고 하자. 또한 반환값은 1까지 도달한 양의 마리수이다. DFS(1)은 DFS(2), DFS(3), DFS(4)를 각각 호출하는데, 결국 DFS(1)은 DFS(2) + DFS(3) + DFS(4) + 0과 같게 된다. DFS(2)는 DFS(5)에서 자신의 노드 정보에따라 양의 수를 연산하고, 그 결과값을 반환하면 된다. DFS(5)의 경우에는 리프노드이므로 5번 노드가 양이라면 양의 마리수를, 늑대라면 양이 없으므로 0을 반환하면 된다. 즉, 각 노드들은, (자식노드까지 온 양의 마리수) + (자신의 늑대/양에 따른 증감 연산)을 반환하면 된다.

양인지 늑대인지 판별하기 위해 bool타입의 isSheep을 사용하였고, 각 노드별로 개체의 마리수를 파악하기 위해 cnt[]를 사용하였다. 입력값에서 해당 노드가 양이면 그대로 대입, 늑대이면 -를 붙혀서 감소연산하도록 했다. dfs()내부에서 감소연산을 했을 때 0미만이 되었다면 0으로 다시 대입 해주어야 한다.

또한 출력값이 int를 초과하므로 더 넓은 범위의 자료형이 필요하다.

BFS로도 풀 수 있을 듯 하다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int n;
multimap<int, int> mm;
bool isSheep[123456];
int cnt[123456];

long long int dfs(int idx) {
	long long int sum = 0;
	auto rg = mm.equal_range(idx);
	
	if (rg.first == rg.second) {
		if (isSheep[idx]) return cnt[idx];
		return 0;
	}
	for (auto& it = rg.first; it != rg.second; it++)
		sum += dfs(it->second);
	sum += cnt[idx];
	if (sum < 0) sum = 0;
	return sum;
}

int main() {
	int in2, in3;
	char in1;
	cin >> n;
	for (int i = 1; i < n; i++) {
		scanf(" %c %d%d", &in1, &in2, &in3);
		if (in1 == 'S') {
			isSheep[i] = true;
			cnt[i] = in2;
		}
		else cnt[i] = -in2;
		mm.insert({ in3 - 1, i});
	}
	cout << dfs(0);
	return 0;
}