글 읽기 - dfs로 작성하였는데 시간초과가납니다.

unilep 6년 전 1

선을 연결하는 가격들의 리스트 중 비싼거 k개는 안내도 되기때문에

정렬을 해야할 필요가 있을거 같았고...

그 가격들의 리스트 valList 를 정렬하기위해

벡터 tmp를 따로 받아서 tmp를 정렬했습니다.

valList를 정렬하면 나중에 pop할때 문제가 생길거같아서요

그런데 시간초과가 나는것을 보니 방법이 틀린거같은데

힌트좀 주실수있나요?

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

typedef pair<int, int> Pair;

int n, p, k, ans = 987654321;
vector<Pair> v[1001];
bool visit[1001], isAnswer;
vector<int> valList;

void dfs(int x) {
	if (isAnswer) return;
	visit[x] = true;

	if (x == n) {
		visit[n] = false;
		int sz = valList.size();
		if (sz <= k) { // 원장은 0원을 내도된다. 더이상 탐색 안해도됨
			ans = 0;
			isAnswer = true;
			return;
		}

		vector<int> tmp; // 현재 가격들을 정렬하기위해
		for (int i = 0; i < sz; i++) tmp.push_back(valList[i]);
		sort(tmp.begin(), tmp.end());
		ans = min(ans, tmp[sz - k - 1]); // 가격들 중에 k개는 안내도된다
		return;
	}

	int sz = v[x].size();
	for (int i = 0; i < sz; i++) {
		Pair& p = v[x][i];
		int next = p.first;
		if (visit[next]) continue;
		valList.push_back(p.second); // next번 선을 연결하는데 드는 비용 추가
		dfs(next); // next 를 연결했다
		valList.pop_back(); // next선을 뺄거기 때문에 pop
	}

	visit[x] = false;
}

int main() {
	cin >> n >> p >> k;
	for (int i = 0; i < p; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		v[from].push_back({ to, cost });
		v[to].push_back({ from, cost });
	}
	
	dfs(1);
	if (ans == 987654321) ans = -1;
	cout << ans;
	return 0;
}

lyzqm 6년 전 1

완전탐색으로는 시간초과가 날겁니다.

다익스트라 알고리즘을 변형해서 해결할 수 있습니다

chogahui05 6년 전 2

코레스코에서는 K개의 선에 대해서는 공짜로 연결해 주기로 했고

나머지 컴에 대해서는 연결 되어있거나 안 되어 있어도 된다.

이 때 남은 것 중 가장 비싼 가격을 x라고 합시다.

만약에 x일 때 연결이 안 되었는데 x-1일 때 연결이 될 수 있을까요?

그리고 K개의 선에 대해서 공짜로 연결을 해 주는 경우에 x를 초과하는 선에 대해서 공짜로 까는 게 이득일까요?

아니면 그렇지 않은 선에 대해서도 공짜로 까는 게 이득일까요?

이 두 힌트를 잘 조합해 보세요.

이 정도면 거의 답을 대놓고 알려드린 수준인데.. 잘 생각해 보세요.

chogahui05 6년 전 1

그런데 백조의 호수는 푸신 거 같으시니까..

이 문제도 아주 조금만 생각해 보시면 충분히 푸실 수 있을 거 같아요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dfs로 작성하였는데 시간초과가납니다.

unilep 6년 전 1

lyzqm 6년 전 1

chogahui05 6년 전 2

chogahui05 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말