코드 복사/붙여넣기 하는 당신이 아름답습니다.

1948 : 임계경로

풀이

문제를 다르게 생각해보자.

마지막에 도착하는 사람까지 도착을 하는 시간 이라는 문장은 결국 가장 먼 길을 선택하는 사람, 즉 최장 거리를 의미한다.

따라서 이 문제는 최장 거리와, 최장 경로들에 포함되는 모든 간선의 개수를 카운팅해서 출력하면 된다!

풀다보니까 이게 개수를 카운팅 할 때 뒤에서 부터 돌아야 할 것 같은데… 인접행렬이 아니라 백터를 써서 짰단 말이야

코드를 다시 짜긴 귀찮고 그래서 dp 배열을 아예 백트랙킹? 그런 느낌으로 구했다.

get_max_len() 함수를 보면 일단 카운팅하기 전에 끝까지 다 들어가놓고, 다시 나오면서 dp[now] = max() 하는 걸 볼 수 있다.

근데 왜 배열 이름을 dp로 했더라

코드

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

struct ABC {
	int idx, val;
	ABC() {}
	ABC(int idx, int val) : idx(idx), val(val) {}
};

int n, m, s, e, ans, dp[10001];
bool chk[10001];
vector<ABC> A[10001];

void get_max_len(int now) {
	for (auto nxt : A[now]) {
		int nn = nxt.idx, nw = nxt.val;
		if (!dp[nn]) get_max_len(nn);
		dp[now] = max(dp[now], dp[nn] + nw);
	}
}

void get_max_cnt(int now) {
	if (chk[now]) return;
	chk[now] = true;
	for (auto nxt : A[now])
		if (dp[nxt.idx] + nxt.val == dp[now])
			++ans, get_max_cnt(nxt.idx);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);
		A[a].push_back(ABC(b, w));
	}
	scanf("%d %d", &s, &e);

	get_max_len(s);
	get_max_cnt(s);

	printf("%d\n%d", dp[s], ans);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-13 12:25

Read more posts by this author