글 읽기 - [c++] 왜 시간초과가 나는지 모르겠습니다..

tizm423 3년 전 0

이분매칭을 생각해서 풀어봤습니다.

문제가 되는 부분은 45번줄부터 시작하는 중첩for문인데

시간초과가 날 이유가 없다고 생각합니다.

혹시 제가 뭘 놓치고 있는걸까요??

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

int N, M, K;
vector<int> adj[1000];
int matched[1001];
bool visited[1000];

bool dfs(int a){
	if(visited[a]) return false;
	visited[a] = true;
	for(int b : adj[a]){
		if(matched[b] == -1 || dfs(matched[b])){
			matched[b] = a;
			return true;
		}
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> K;
	for(int i=0; i<N; i++){
		int count;
		cin >> count;
		while(count--){
			int num;
			cin >> num;
			adj[i].push_back(num);
		}
	}
	
	int count = 0;
	fill(matched, matched+M+1, -1);
	for(int i=0; i<N; i++){
		fill(visited, visited+N, false);
		if(dfs(i)) count++;
	}
	
    // 문제가 되는 부분
	int L = K;
	for(int j=0; j<L; j++){
		for(int i=0; i<N; i++){
			fill(visited, visited+N, false);
			if(dfs(i) && K) {
				count++;
				K--;
				break;
			}
		}
	}
	cout << count << "\n";
}

djm03178 3년 전 1

그 부분이 루프를 이중으로 돌기 때문에 O(N^2)인데, dfs 한 번 할 때마다 visited를 초기화하므로 O(N^2) 시간이 걸려서 총 O(N^4) 시간이 걸립니다.

tizm423 3년 전 0

아하.. 그래서 중간에 빠져나와야 시간안에 답을 받을 수 있던거군요!!

답변 감사드립니다!!ㅎㅎ

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

문제

문제

출처

ICPC

[c++] 왜 시간초과가 나는지 모르겠습니다..

tizm423 3년 전 0

djm03178 3년 전 1

tizm423 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말