백준 1005 ACM Craft

처음 접근 방법

1. goal에서부터 1로 이어진 간선들을 따라 거꾸로 이동하며 time의 합을 구한다

2. 1에 도착하면 합을 리턴한다

3. 1~2번 과정을 goal에 연결된 모든 간선에다가 하고 리턴된 합 중에 max값을 출력

 

그래서 처음에 그래프에 간선을 거꾸로 넣었고 ( v[b].push_back(a); )

go함수에서도 거꾸로 재귀가 돌았다

 

한 가지 의문인 점이 있었는데, 처음에 함수를 int형으로 만들어서 sum매개변수에 연산 후 return sum으로 했다

그러니까 아래 코드 기준으로 하면 int go(int now, int sum) { 연산 종료 조건 시 return sum; 아니면 재귀 } 이런 식이었음

근데 분명 재귀도는 함수의 종료 조건 if문 걸려 들어가서 return하기 직전 즉, return 바로 위에다가 cout<<sum; 을 하면 sum이 잘 나오는데, return sum; 을 main함수에서 받자마자 무슨 값을 리턴해도 1을 받는 기이한 일이 생김

아니 내가 방금 리턴한 sum변수는 어디로 갔는가;;

그래서 재귀 도는 함수 안에 매개변수 sum과 int ssum; 을 두고 ssum = sum; 으로 해 봤는데도 왠지 안 되는 거임..

이렇게 재귀 돌면서 연산 후에 값을 리턴하는 거 엄청 썼는데 이제까지 어케 썼는지 기억이 나지 않더라 뭐지?

솔직히 해결은 못했는데ㅋㅋ 문제 풀어야 하니까 그냥 일단 void함수로 바꾸고 sum을 전역 변수로 둬서 처리했다

문제 풀이 이전에 코딩을 못하니 거 참.. 그나마 할 줄 아는 게 c/c++인데 그것도 애매하게 하네

 

 

처음 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
using namespace std;
vector<int> order[1001];
int time[1001];
int s = 0;
void go(int now, int sum) {
	if (now == 1) {
		s += time[now-1];
		return;
	}
	for (int i = 0; i < order[now].size(); i++) {
		//cout << "go: " << order[now][i] << " " << time[now-1] << endl;
		go(order[now][i], s += time[now-1]);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int t, n, k, goal;
	cin >> t;
	while (t--) {
		cin >> n >> k;

		memset(time, 0, sizeof(time));
		for (int i = 0; i < 1001; i++) order[i].clear();

		for (int i = 0, a; i < n; i++) {
			cin >> a; time[i] = a;
		}
		for (int i = 0, a, b; i < k; i++) {
			cin >> a >> b;
			order[b].push_back(a);
		}
		cin >> goal;

		int res = 0;
		for (int i = 0; i < order[goal].size(); i++) {

			s += time[goal - 1];
			go(order[goal][i], time[goal-1]);
			if (s > res) res = s;
			s = 0;
		}
		cout << res << '\n';
	}

}

일단 답은 잘 나오니까 접근은 제대로 했음

근데 결과는 당연히 시간초과ㅎㅎ;

위상 정렬을 생각하지 못하고 깡으로 찾는 방법으로 구현했다

 

위상 정렬은 그래프에서 반드시 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈 수 있는(방문할 수 있는) 조건이 주어질 때 사용한다

 

큐를 사용해서 구현하는데.. 수행 과정 foxtrotin.tistory.com/358

 

 

맞은 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <queue>
using namespace std;
vector<int> order[1001];
int time[1001], cnt[1001], res[1001]; //자신으로 들어오는 간선의 개수
int s = 0; //sum
queue<int> q;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int t, n, k, goal;
	cin >> t;
	while (t--) {
		cin >> n >> k;

		memset(time, 0, sizeof(time));
		memset(cnt, 0, sizeof(cnt));
		memset(res, 0, sizeof(res));
		for (int i = 0; i < 1001; i++) order[i].clear();

		for (int i = 1; i <= n; i++) cin >> time[i];

		for (int i = 0, a, b; i < k; i++) {
			cin >> a >> b;
			order[a].push_back(b);
			cnt[b]++;
		}
		cin >> goal;

		for (int i = 1; i <= n; i++) { //in-degree가 0인 정점 찾기
			if (cnt[i] == 0) q.push(i);
		}

		while (!q.empty()) {
			int now = q.front();
			q.pop();
			for (int next : order[now]) {
				res[next] = max(res[next], res[now] + time[now]);
				cnt[next]--; //간선 제거
				if (cnt[next] == 0) q.push(next);
			}
		}

		cout << res[goal] + time[goal] << '\n';
	}
}

go함수에 있던 연산을 큐 써서 위상 정렬로 바꿨고

시간을 저장하는 res배열을 두고 max(다음 시간, 현재까지 시간+현재 시간)으로 최대 시간을 쟀다