글 읽기 - 완전탐색 시간초과가 납니다

freewizard 5년 전 0

안녕하세요,

현재 시간초과가 나는데 이 코드에서 더 효율화할 부분이 있을까요?

미리 감사드립니다

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

int board[10][10];
int n;

int solve(int m, unordered_set<int> set, vector<int> buffer) {
	if (m == 0) {
		int tot = 0;
		
		for (int i = 0; i < buffer.size(); i++) {
			if (i == buffer.size() - 1) {
				if (board[buffer[i]][buffer[0]] == 0) {
					tot = 999999999;
					break;
				}
				else {
					tot += board[buffer[i]][buffer[0]];
				}
			}
			else {
				if (board[buffer[i]][buffer[i + 1]] == 0) {
					tot = 999999999;
					break;
				}
				else {
					tot += board[buffer[i]][buffer[i + 1]];
				}
			}
		}
		if (tot == 30) {
			for (int i = 0; i < buffer.size(); i++) {
				cout << buffer[i] << " ";
			}
			cout << endl;
		}
		return tot;
	}

	int ret = 999999999;
	for (int i = 0; i < n; i++) {
		if (set.find(i) == set.end()) {

			set.insert(i);
			buffer.push_back(i);
			ret = min(ret, solve(m - 1, set, buffer));
			buffer.pop_back();
			set.erase(i);

		}
	}
	return ret;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
	vector<int> tmp;
	tmp.reserve(10);
	cout << solve(n, unordered_set<int>(), tmp) << '\n';
}

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

문제

문제

출처

ICPC

완전탐색 시간초과가 납니다

freewizard 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말