글 읽기 - 1005번 ACM Craft 시간초과....

gkfkagkfka12 6년 전 0

위상정렬을 이용해서 풀었는데 시간초과가 발생합니다 ㅠㅠ

어떻게 개선할 수 있을까요?

질문검색에 있는 예제들로 답은 맞는것 같습니다.

#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>

int building_time[1000 + 1]; // 건물시간(계산에 이용되는 배열)
int dp[1000 + 1]; // 건물시간(고정)
int indegree[1000 + 1]; // 진입차수

int main(void)
{
	int tc, N, K, o1, o2, W; scanf("%d", &tc);
	std::vector<int>* graph; // 인접리스트 그래프
	std::queue<int> search; // 탐색을 하는 큐

	while (tc--){
		// 건물 수, 연결 수 입력받고 동적으로 벡터배열 할당
		scanf("%d %d", &N, &K);
		graph = new std::vector<int>[N + 1];

		// 건물짓는 시간을 입력받아 building_time 배열 초기화
		// 그 값으로 dp 배열 초기화
		for (int i = 1; i <= N; i++){
			scanf("%d", &building_time[i]);
			dp[i] = building_time[i];
		}

		// 각 정점들을 입력받아 graph 벡터로 연결
		// 또 각 정점들의 진입차수 계산
		for (int i = 1; i <= K; i++){
			scanf("%d %d", &o1, &o2);
			graph[o1].push_back(o2);
			indegree[o2]++;
		}

		// 도달해야 하는 건물 번호 입력
		scanf("%d", &W);

		// 모든 정점 중에 진입차수가 0인 정점을 search 큐에 push
		for (int i = 1; i <= N; i++)
			if (indegree[i] == 0) search.push(i);

		// W의 진입차수가 0이 되면 빠져나온다.
		while (indegree[W]){			
			// search 큐가 비어있지 않다면 실행
			if (search.size()){
				// front함수를 많이 호출하기 때문에 변수로 저장
				int front_search = search.front();

				for (int i = 0; i < graph[front_search].size(); i++){
					// search 큐의 데이터에 연결되어있는 모든 정점의 진입차수를 줄인다.
					indegree[graph[front_search][i]]--;
					if (indegree[graph[front_search][i]] == 0) search.push(graph[front_search][i]);

					// search 큐에 들어가는 순서 자체가 위상 정렬 순서이기 때문에
					// 따로 위상 정렬 큐를 선언하지 않고 바로바로 계산한다.
					dp[graph[front_search][i]] =
						std::max(dp[graph[front_search][i]], dp[front_search] + building_time[graph[front_search][i]]);
				}

				// search 큐의 데이터를 pop
				search.pop();
			}
		}

		// 그렇게 계산이 완료된 도달정점까지의 시간을 출력
		printf("%d\n", dp[W]);

		for (int i = 1; i <= N; i++){
			indegree[i] = 0;
			dp[i] = 0;
		}

		delete[] graph;
	}

	return 0;
}

juhongkim2 6년 전 0

cin, cout은 scanf, printf보다 훨씬 느립니다

scanf, printf를 써보시길....

그리고 그거 고쳐도 틀렸습니다가 나오는데

잘 찾아보시면 뭐가 틀린지 아실 수 있을것입니다...

gkfkagkfka12 6년 전 0

댓글 감사합니다.

그런데 printf,scanf로 바꿔도 시간초과가 납니다....

juhongkim2 6년 전 0

cin,cout전부 다 바꾸셨나요???

소스 그대로 복사해서 cin,cout부분 전부다 scanf,printf로 바꾸니 시간초과가 아니라 런타임에러가 나오네요

참고로

이런 문제처럼 while로 여러 테스트케이스를 다 받아주는 문제는 전역변수로 선언해놓은 부분 초기화를 잘 해주셔야 합니다

이 문제에서 indegree배열의 경우 전역변수로 선언해 놓으셨는데 while안쪽에 indegree배열을 초기화 하는 부분이 없습니다

indegree배열을 초기화하지 않으면 어떻게 될까요...?

gkfkagkfka12 6년 전 0

33퍼센트에서 계속 시간초과가 나와서 다시 코드를 더 줄였습니다.

다 scanf,printf로 바꿨는데도 33퍼센트에서 시간초과가 발생했네요...

그리고 전역변수는 선언하는 순간 0으로 초기화됩니다.

juhongkim2 6년 전 1

전역변수는 프로그램이 시작하면서 할당되어 프로그램이 끝날 때 까지 존재하는 변수입니다.

지금 while문으로 여러 테스트케이스를 돌려야하는 상황인데

테스트 케이스가 2개가 들어온다고 치면

첫번째 케이스는 indegree배열이 모두 0으로 초기화 된 상태라 아무 문제없이 돌아갑니다

그런데 전역변수로 선언한 indegree배열은 두번째로 while문을 돌때 자동으로 0으로 초기화되지 않습니다

디버깅 해보시면 잘 확인하실 수 있을듯...

위에 수정하신 코드

27째 줄에 memset(indegree,0,sizeof(indegree));를 추가해서

indegree배열을 0으로 초기화해주면 시간초과가 아니라 틀렸습니다가 나옵니다

제 생각에 지금코드에서 시간초과가 나는 이유는 그거 같습니다

44번째 줄 while문을 indegree[W]가 0이 될때까지 돌리는데

indegree배열을 초기화 안하시면 테스트케이스를 돌때마다 indegree배열에 저장된 값이 축적되서 엄청커집니다...

그래서 시간초과가 나는듯하네요...

djm03178 6년 전 1

초기화 문제는 매 tc마다 기존의 dp 배열이 그대로 남아있다는 데에 있습니다.

그리고 graph도 전체 tc 중 마지막 것에 대해서만 delete 되고 나머지는 계속 미아가 되겠네요.

gkfkagkfka12 6년 전 0

아 무슨 말인지 이해했습니다. 감사합니다!

시간초과는 해결했네요... 근데 틀렸습니다에 대한 부분은 힌트 좀 주실 수 있나요?

질문 검색 다 돌아보면서 예제 다 확인했는데 다 맞는데....ㅠㅠ

djm03178 6년 전 1

W가 마지막에 방문할 정점이라는 보장도 없기 때문에 큐도 테스트 케이스마다 비워주어야 합니다.

gkfkagkfka12 6년 전 0

답글 달아주신 @juhongkim2, @djm03178님 모두 감사드립니다!!

초기화에 대해서 한번 더 생각할 수 있는 시간이었습니다.

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

문제

문제

출처

ICPC

1005번 ACM Craft 시간초과....

gkfkagkfka12 6년 전 0

juhongkim2 6년 전 0

gkfkagkfka12 6년 전 0

juhongkim2 6년 전 0

gkfkagkfka12 6년 전 0

juhongkim2 6년 전 1

djm03178 6년 전 1

gkfkagkfka12 6년 전 0

djm03178 6년 전 1

gkfkagkfka12 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말