글 읽기 - 시간 초과를 어떻게 해결해야되는지 잘 모르겠습니다

tlfla01 6년 전 0

그래프를 막 공부하고 있는 초보자입니다. 제가 작성한 소스에서 어디서 시간초과가 나는지 잘 이해가 되지 않아서 고수분들께 도움을 요청합니다. 제발 도와주세요 ㅜㅜ

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>

#define SIZE 100001

using namespace std;

int adj[SIZE];
int visited[SIZE];
int check[SIZE];

queue<int> q;
vector<int> store; //해당 노드에서 연결되는 지점들을 모두 저장하는 vector

void bfs(int now) {
	q.push(now);
	
	while (!q.empty()) {
		int front = q.front();
		store.push_back(front); //vector에 방문지점들 저장
		
		if (!visited[adj[front]] && !check[adj[front]]) { //방문하지 않고 사이클로 체크되지 않은 지점이라면
			q.push(adj[front]);
			visited[adj[front]] = true;
			check[adj[front]] = true;
		}		
		q.pop(); 
	}	
}
int main() {
	int t;
	scanf("%d", &t);

	while (t--) {
		int n;
		int cycle=0;

		memset(check, false, sizeof(check));

		scanf("%d", &n);

		for (int i = 1; i <= n; i++)
			scanf("%d", &adj[i]);

		for (int i = 1; i <= n; i++) {			
			memset(visited, false, sizeof(visited));
			store.clear();
						
			if(!check[i]) //사이클로 인정되지 않은 지점만 함수 실행
				bfs(i);
			
			if (store.size() > 1) {
				// 함수 실행 후 만들어진 vector를 가지고 사이클 판별
				// 사이클이면 store에 저장된 첫번째 값과 끝 값이 같음
				if (store[0] == store[store.size() - 1]) 
					cycle += store.size() - 1; //사이클로 인정되면 갯수 증가 && 해당 check의 true값들은 그대로 남아있음
				
				else
					for (int j = 0; j < store.size(); j++)
						check[store[j]] = false; //사이클로 인정되지 않으면 해당 check의 값들을 false 로 초기화
			}
		}		
		printf("%d\n", n-cycle);
	}
}

kdk8361 6년 전 1

100000

2 3 4 5 6 ....... 99998 99999 100000 100000

이 케이스의 경우 i가 1부터 n까지 돌아갈 때 n, n-1, n-2, n-3,,,, 1

O(n^2)번 돌아갑니다.

bfs나 dfs를 돌린 후 그걸 초기화 하지 않고 그대로 써먹을 수 있습니다. 곰곰이 생각해 보세요

tlfla01 6년 전 0

아직 초기화를 한다는 생각을 버리지를 못해서요 ㅜㅜ

각 노드는 한개의 노드만 가리킨다는 생각을 기반으로 사이클이 아닌 경우 vector에 들어있는 노드들 중 마지막 노드만 해당 check를 초기화 시켜주어서 O(n^2) 으로 의심가는 초기화 반복문을 줄여봤는데 그래도 시간 초과가 뜨네요.. 혹시 조그마한 힌트 하나만 더 주실 수 있으신가요??

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>

#define SIZE 100001

using namespace std;

int adj[SIZE];
int visited[SIZE];
int check[SIZE];

queue<int> q;
vector<int> store; //해당 노드에서 연결되는 지점들을 모두 저장하는 vector

void bfs(int now) {
	q.push(now);
	
	while (!q.empty()) {
		int front = q.front();
		store.push_back(front); //vector에 방문지점들 저장
		
		if (!visited[adj[front]]) { //방문하지 않고 사이클로 체크되지 않은 지점이라면
			q.push(adj[front]);
			visited[adj[front]] = true;
			check[adj[front]] = true;
		}
		q.pop(); 
	}		
}
int main() {
	int t;
	scanf("%d", &t);

	while (t--) {
		int n;
		int cycle=0;

		memset(check, false, sizeof(check));

		scanf("%d", &n);

		for (int i = 1; i <= n; i++)
			scanf("%d", &adj[i]);

		for (int i = 1; i <= n; i++) {			
			memset(visited, false, sizeof(visited));
			store.clear();
						
			if(!check[i]) //사이클로 인정되지 않은 지점만 함수 실행
				bfs(i);
			
			if (store.size() > 1) {
				// 함수 실행 후 만들어진 vector를 가지고 사이클 판별
				// 사이클이면 store에 저장된 첫번째 값과 끝 값이 같음
				if (store[0] == store[store.size() - 1])
					cycle += store.size() - 1; //사이클로 인정되면 갯수 증가 && 해당 check의 true값들은 그대로 남아있음

				else
					check[store[store.size() - 1]] = false; //사이클이 아니면 마지막 인자의 check만 초기화하여 해당 노드에서 함수를 실행할 수 있게함					
			}
		}		
		printf("%d\n", n-cycle);
	}
}

chogahui05 6년 전 0

한 사람이 2 사람 이상을 선택할 수 있을까요?

이 질문에 대한 답을 먼저 해 보시면 어떻게 푸셔야 할 지 아실 수 있을 듯 싶네요.

잘 안 되시는 경우에는 위상 정렬도 고려해 보세요.

특수한 케이스의 그래프에서는 사이클을 탐지하는 데 위상정렬을 써도 나쁘지 않습니다.

이 문제에 나오는 그래프 구조가 위상 정렬을 써도 되는 구조인지는 알려드리지 않겠습니다.

kdk8361 6년 전 0

정점에서 나가는(방향있는) 간선이 단 하나인 그래프일 경우 탐색을 하던 도중 이미 체크를 한 부분을 만났을 때

그 체크 했다는 사실이 어떤 의미를 가지는지, 의미가 있는지 없는지 한번 생각해 보시는게 좋을 것 같습니다.

이미 문제에 첨부되어 있는 예제가 아주 좋은 예제라고 생각해요.

tlfla01 6년 전 0

해당 소스에서 bfs로 풀던걸 dfs로 바꿔서 풀어봤습니다.

각 노드별로 돌다가 해당 경로가 사이클일때만 사이클임을 표기하는 새로운 함수를 돌리는 방법으로 구상해봤는데 다행히 돌아가더군요!!

답변주신분들 정말 감사드립니다!!

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

문제

문제

출처

ICPC

시간 초과를 어떻게 해결해야되는지 잘 모르겠습니다

tlfla01 6년 전 0

kdk8361 6년 전 1

tlfla01 6년 전 0

chogahui05 6년 전 0

kdk8361 6년 전 0

tlfla01 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말