1005 - ACM Craft

첫번째 풀이

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

int T,N,K;
int X, Y, W;
int building[1001];
int dist[1001];
int ans;
vector<vector<int>>v;


void dfs(int start) {
	if (start == W) {
		if (ans < dist[W]) { ans = dist[W]; return; }
	}


	for(int i = 0; i < v[start].size(); i++) {
		int next = v[start][i];
		if (dist[next] < dist[start] + building[next]) {
			dist[next] = dist[start] + building[next];
		}
		dfs(next);
	}
	
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	while (T--) {
		cin >> N >> K;
		v.resize(N+1);
		for (int i = 1; i <= N; i++) {
			cin >> building[i];
		}
		for (int i = 0; i < K; i++) {
			cin >> X >> Y;
			v[X].push_back(Y);
		}
		cin >> W;
		for (int i = 1; i <= N; i++) {
			for (int i = 1; i <= N; i++) {
				dist[i] = building[i];
			}
			dfs(i); 
		}

		cout << ans << '\n';

		ans = 0;
		memset(dist, 0, sizeof(dist));
		v.clear();
	}
	
	
	return 0;
}

완전탐색으로 bfs, dfs로 푸니 시간초과, 메모리초과가 났다.

for (int i = 1; i <= N; i++) {
			for (int i = 1; i <= N; i++) {
				dist[i] = building[i];
			}
			dfs(i); 
		}

여기서 dfs(i)를 계속 호출해서 시간이 많이 걸렸고 dfs가 visited가 없어서 엄청난 시간이 소요된다.

---

두번째 풀이

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

int T,N,K;
int X, Y, W;
int building[1001];
int ans;
bool visited[1001];
vector<vector<int>>v;


void dfs(int start, int sum) {
	if (ans < sum) {
		ans = sum;
	}

	for(int i = 0; i < v[start].size(); i++) {
		int next = v[start][i];
		if (!visited[next]) {
			dfs(next, sum + building[next]);
		}
	}
	
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	while (T--) {
		cin >> N >> K;
		v.resize(N+1);
		for (int i = 1; i <= N; i++) {
			cin >> building[i];
		}
		for (int i = 0; i < K; i++) {
			cin >> X >> Y;
			v[Y].push_back(X);
		}
		cin >> W;

		dfs(W, building[W]);
		

		cout << ans << '\n';

		ans = 0;
		memset(visited, 0, sizeof(visited));
		v.clear();
	}
	
	
	return 0;
}

생각을 전환하여 방향그래프의 방향을 반대로 설정해주어 W에서 가장 큰 길이를 구해주면 답이나올 것 같았다.

위 방법으로 하면 dfs(i)모든 경우 탐색을 줄일 수 있다.
하지만 여기서도 시간초과가 뜬다.

---

정답 코드

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

int T,N,K;
int X, Y, W;
int building[1001];
int ans;
bool visited[1001][1001];
int dp[1001];
vector<vector<int>>v;

int dfs(int start) {
	if (dp[start] != 0) { return dp[start]; } // W->start까지 저장되어있으면 리턴
	int M=0;
	for(int i = 0; i < v[start].size(); i++) {
		int next = v[start][i];
		if (!visited[start][next]) { // next에 방문하지 않았다면
			visited[start][next] = true; // 방문처리 후
			M=max(M,dfs(next)); // 다음으로 간다.
		}
	}

	return dp[start]=M + building[start]; // dfs로 끝까지 파고 들어서 리턴해주며 맨 끝 노드부터 하나씩 거리를 계산
	
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	while (T--) {
		cin >> N >> K;
		v.resize(N+1);
		for (int i = 1; i <= N; i++) {
			cin >> building[i];
		}
		for (int i = 0; i < K; i++) {
			cin >> X >> Y;
			v[Y].push_back(X);
		}
		cin >> W;

		cout << dfs(W) << '\n';

		ans = 0;
		memset(dp, 0, sizeof(dp));
		memset(visited, 0, sizeof(visited));
		v.clear();
	}
	
	
	return 0;
}

dp 메모이제이션으로 dp테이블에 저장해주며 중복을 줄여서 정답이 나왔다.

얻은 것

1. visited없이 dfs, bfs는 시간소요가 엄청나다
2. 재귀를 이용한 메모제이션 방법 숙달