[구름 알고리즘 먼데이 챌린지] Week8 : 4. 구름나라 청소하기

문제

구름나라는 N개의 도시와 N - 1개의 도로로 이루어진 나라이다. 각 도시는 1번부터 N번까지 번호가 붙어있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있으며, 같은 두 도시 쌍을 잇는 도로는 존재하지 않는다.

 

최근 구름나라의 도시들에는 불법 쓰레기 투기로 인한 환경적 문제가 발생하고 있다. 때문에 현재 i

번 도시에는 Ai만큼의 쓰레기가 쌓여 있는 상태이다. 구름나라의 청소부인 구름이는 구름나라를 돌아다니면서 쓰레기들을 치우려고 한다.

 

구름이는 최대 K만큼의 쓰레기를 담을 수 있는 커다란 쓰레기 봉투를 가지고 있다. 구름이는 현재 1번 도시에 있고, 다음 두 가지 행동들을 자유롭게 반복하여 청소를 하고자 한다. 구름이가 현재 머물고 있는 도시를 a번 도시라고 하자.

• a번 도시에 인접한 도시 중 하나로 이동한다. 이 때, 이미 방문한 도시로는 갈 수 없다.
• a번 도시를 깨끗하게 청소한다. 청소를 하게 되면 구름이의 쓰레기 봉투가 Ai만큼 차게 된다. 단, a 번 도시를 이미 청소했거나, 현재 쓰레기 봉투에 담긴 쓰레기의 양과 Ai를 합친 값이 K보다 커진다면 청소를 할 수 없다.

구름이는 효율적으로 봉투를 쓰기 위해, 쓰레기 봉투에 가능한 많은 양의 쓰레기를 담아서 버리려고 한다. 구름이가 모을 수 있는 쓰레기 양의 최댓값을 구해보자.

---

입력

첫 번째 줄에는 구름나라의 도시의 수 N(1 <= N <= 1,000)

과 구름이가 들고 있는 쓰레기 봉투의 용량 K(0 <= K <= 50,000)

가 공백으로 구분되어 주어진다. 

 

다음 N - 1개의 줄에는 구름나라의 도로가 잇는 두 도시의 번호 u,v(1 <= u, v <= N, u != v)

가 공백으로 구분되어 주어진다.

 

그 다음 줄에는 도시에 쌓인 쓰레기의 양을 의미하는 A1, A2, ... , AN (0 <= Ai <= 50)이 공백으로 구분되어 주어진다.

---

도시의 수와 도로의 수가 크지 않은 것 같아 DFS와 백트래킹을 활용한 완전탐색 문제로 판단했다.

문제에서 주어진 대로 현재 도시에서 청소를 한 뒤 다음 도시로 이동하는 것과 청소를 하지 않고 바로 다음 도시로 이동하는 모든 경우의 수를 탐색하며 최대로 처리할 수 있는 쓰레기의 양을 구하고자 했다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, K, u, v, ans;
vector<int> edge[1001];
vector<int> trash(1001, 0), visited(1001, 0);

void dfs(int cur, int capacity) {
    visited[cur] = 1;
    //1)일단 현재 도시에서 청소를 진행
    int afterClean = capacity + trash[cur];
    //2)봉투의 용량이 초과 되지 않아 성공적으로 청소가 가능한 경우 최댓값 갱신
    if (afterClean <= K && afterClean > ans) ans = afterClean;
    //3)현재 도시 기준으로 도로가 연결된 이웃 도시 탬색
    for (auto& next : edge[cur]) {
        if (ans == K) return; //이미 최대값을 구한 경우 탐색 종료
        if (visited[next]) continue; //같은 도시 중복 방문 방지
        //현재 도시를 청소할 수 있는 경우 청소 진행 후 다음 도시로 이동
        if (afterClean <= K && trash[cur] != 0) {
            dfs(next, afterClean);
            visited[next] = 0;
        }
        //청소를 하지 않고 바로 다음 도시로 이동
        dfs(next, capacity);
        visited[next] = 0;
    }
}

void input() {
    cin >> N >> K;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for (int i = 1; i <= N; i++) cin >> trash[i];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    input();
    //K가 0이거나 모든 도시의 쓰레기 양이 K보다 큰 경우 0 출력 후 종료
    int minCapacity = *min_element(trash.begin(), trash.end());
    if (K < minCapacity) { cout << 0; return 0;}
    dfs(1, 0);
    cout << ans;
    return 0;
}

 

각 도시에 쌓인 쓰레기 양 Ai가 0일 수 있다는 점과 K 또한 0일 수 있다는 조건에 따라

위와 같은 경우 불필요한 DFS를 수행하지 않도록 조건을 추가해 주었다.

하지만, 완탐으로 구현할 경우 가능한 효율적으로 조건들을 추가해 주었음에도 불구하고 55번 케이스에서의 시간초과를 해결하지 못했다.

 

 문제 오류를 의심하여 해설을 보았지만 아쉽게도 완전탐색 유형의 문제가 아닌 듯 했다.

결론부터 말하면 DFS와 동적 프로그래밍(DP)를 활용하여 문제를 해결해야 한다.

구름에서 제공하는 해설에 사족을 좀 붙여 설명해보자.

일단 DFS탐색으로 1번부터 가능한 모든 도시를 방문해야 하는 것은 정답이다.

이후, 1번 도시부터 순서대로 방문하는 도시(cur)마다 cur도시가 0~50까지 중 가질 수 있는 쓰레기 처리량을 모두 찾아 주는 것이다.

 

1.현재 도시(cur) 이전의 도시(prev)가 그 capacity를 가지는 경우 현재 도시도 해당 capacity를 가질 수 있음.

->현재 도시를 청소 하지 않으면 현재 도시도 해당 capacity를 가질 수 있기 때문

2.현재 도시(cur) 이전의 도시(prev)가 그 capacity를 가지는 경우 현재 도시는 capacity + 현재 도시의 쓰레기 양 만큼의 capacity를 가질 수 있다.

->현재 도시를 청소 한다면 이전 도시에서의 capacity + 현재 도시의 쓰레기 양 만큼의 capacity를 가질 수 있음.

 

조금 더 이해하기 쉽게 해설 정답 코드에 주석을 추가해 주었다.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1004, BIT = 50005;
bool dp[MAX][BIT], can[BIT];
int A[MAX], N, K;
vector<int> G[MAX];

void DFS(int cur, int prev) {
	for (int i = 0; i <= K; ++i) {

		if (dp[prev][i]) { //이전 도시가 해당 capacity(=i)를 가지는 경우
			//청소를 하지 않으면 현재 도시도 해당 capacity를 가질 수 있음
			can[i] = dp[cur][i] = 1;
			//청소를 하는 경우 해당 capacity + 현재 도시의 쓰레기 양(=i + A[cur])만큼의 capacity를 가질 수 있음
			if (i + A[cur] <= K) can[i + A[cur]] = dp[cur][i + A[cur]] = 1;
		}
	}
	//다음 도시로 이동
	for (int& next : G[cur]) {
		if (next == prev) continue; //이전 도시 중복 방문 방지
		DFS(next, cur);
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i < N; ++i) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i = 1; i <= N; ++i) cin >> A[i];
	dp[0][0] = 1;
	DFS(1, 0);
	//처리할 수 있는 최대 쓰레기 양을 구하기 위해 끝에서 부터 탐색
	for (int i = K; i >= 0; --i) {
		if (can[i]) {
			cout << i;
			return 0;
		}
	}
	return 0;
}