글 읽기 - C구현] 시간 초과 문제입니다. 꼭 좀 도와주세요

heavensun 6년 전 0

안녕하세요.

제가 구현해야 하는 환경은 C 의 경우 stdio.h & malloc.h 만 사용가능하고, c++ 의 경우도 STL 만 사용가능합니다.

그래서 간선리스트를 이용해 edge 데이터를 저장하고, 각 유형별로 bfs 로 정답을 접근했습니다.

하지만 비슷한 유형의 문제에서 데이터가 큰 경우 시간 초과 문제가 발생합니다.

그래서 본 문제에서 위와 같은 제약 사항에서 꼭 해결을 해 보고 싶습니다.

가능하시다면 주의해야 할 부분과 아래 소스에서 잘못된 부분에 대해서 조언 부탁드립니다.

일단 기본적으로 예제 데이터는 통과하고, 제출했을 때는 시간 초과가 나서 최종 정답 여부는 아직 확인 못한 상태입니다.

#include <stdio.h>

struct edge {
	int from;
	int to;
};

typedef struct edge EDGE;

EDGE e[1000001];
int cnt[100001];
int check[100001];
int queue[100001];
int front;
int end;

void clear() {
	for (int i = 0; i < 100001; i++) {
		check[i] = 0;
	}
	front = 0;
	end = 0;
}

void quicksort(EDGE *base, int left, int right) {

	int mleft = left;
	int mright = right;
	int pivot = base[(mleft + mright) / 2].from;

	while (mleft < mright) {
		while (base[mleft].from < pivot) mleft++;
		while (base[mright].from > pivot) mright--;

		if (mleft <= mright) {
			if (base[mleft].from != base[mright].from) {
				int tfrom = base[mleft].from;
				int tto = base[mleft].to;
				base[mleft].from = base[mright].from;
				base[mleft].to = base[mright].to;
				base[mright].from = tfrom;
				base[mright].to = tto;
			}
			mleft++;
			mright--;
		}
	}
	if (mleft < right) {
		quicksort(base, mleft, right);
	}
	if (mright > left) {
		quicksort(base, left, mright);
	}
}

void bubblesort(EDGE *base, int n) {

	for (int i = 1; i <= n - 1; i++) {
		for (int j = 1; j <= n - 1; j++) {
			if (base[j].from > base[j + 1].from) {
				int tfrom = base[j].from;
				int tto = base[j].to;
				base[j].from = base[j + 1].from;
				base[j].to = base[j + 1].to;
				base[j + 1].from = tfrom;
				base[j + 1].to = tto;
			}
		}
	}

}

int bfs1(int citya, int cityb, int cityg1, int cityg2) {
	int ans = 0;

	check[citya] = 1;
	queue[end] = citya;
	end++;

	while (front < end) {
		int curPcity = queue[front];
		front++;

		for (int i = cnt[curPcity - 1] + 1; i <= cnt[curPcity]; i++) {
			int nextCity = e[i].to;
			if ((curPcity == cityg1 && nextCity == cityg2) || (curPcity == cityg2 && nextCity == cityg1)) {
				continue;
			}
			if (check[nextCity] == 1) continue;

			if (nextCity == cityb) return 1;
			
			check[nextCity] = 1;
			queue[end] = nextCity;
			end++;
		}
	}

	return 0;
}

int bfs2(int citya, int cityb, int cityc) {
	int ans = 0;

	check[citya] = 1;
	queue[end] = citya;
	end++;

	while (front < end) {
		int curPcity = queue[front];
		front++;

		for (int i = cnt[curPcity - 1] + 1; i <= cnt[curPcity]; i++) {
			int nextCity = e[i].to;
			if (nextCity == cityc) {
				continue;
			}
			if (check[nextCity] == 1) continue;

			if (nextCity == cityb) return 1;

			check[nextCity] = 1;
			queue[end] = nextCity;
			end++;
		}
	}

	return 0;
}

int main() {
	int vn;
	int en;
	int ansnum;
	int anstype;
	int ansval1, ansval2, ansval3, ansval4;

	scanf("%d %d", &vn, &en);

	for (int i = 1; i <= en; i++) {
		scanf("%d %d", &e[i].from, &e[i].to);
		e[i + en].from = e[i].to;
		e[i + en].to = e[i].from;
	}

//	bubblesort(e, 2 * en);

	quicksort(e, 1, 2 * en);

	for (int i = 1; i <= 2 * en; i++) {
		cnt[e[i].from]++;
	}

	for (int i = 1; i <= vn; i++) {
		cnt[i] = cnt[i - 1] + cnt[i];
	}

	scanf("%d", &ansnum);
	for (int i = 0; i < ansnum; i++) {
		scanf("%d", &anstype);

		if (anstype == 1) {
			int ans = 0;
			scanf("%d %d %d %d", &ansval1, &ansval2, &ansval3, &ansval4);

			ans = bfs1(ansval1, ansval2, ansval3, ansval4);
			printf("%s\n", ans?"yes":"no");
		}
		else {
			int ans = 0;
			scanf("%d %d %d", &ansval1, &ansval2, &ansval3);
			ans = bfs2(ansval1, ansval2, ansval3);
			printf("%s\n", ans ? "yes" : "no");
		}
		clear();
		
	}


	return 0;
}

sgchoi5 6년 전 1

CHCI 문제는 정답도 제공이 되고, 대회 때 사용한 TC 도 제공이 되니.. 급하시면 받아서 해보시길..

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

C구현] 시간 초과 문제입니다. 꼭 좀 도와주세요

heavensun 6년 전 0

sgchoi5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말