글 읽기 - 시간초과가 발생하는 이유가 무엇인지 모르겠습니다.

dladydwo123 5년 전 0

재방문을 막기위한 table과, 사이클 길이를 O(1)으로 출력하기 위한 check 배열. 부분 사이클 여부를 판단하는 check_table 배열로 이루어져 있습니다.

for(;;) 부분에서 무언가의 이유로 무한루프를 도는게 아닐까? 생각해봤지만, 이유를 못찾았습니다. 새벽에 졸린 상태로 계속 붙잡고 있어서 집중도 안돼고....

제발 도와주시길 부탁드립니다.

#include<cstdio>
#include<cstring>

int T, N;
bool table[100001] = { 0, };
int info[100001] = { 0, };
int check[100001] = { 0, };

int main() {
	scanf("%d", &T);
	for (int I = 0; I < T; I++) {
		memset(table, 0, sizeof(table));

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

		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			if (table[i] == 0) {
				bool check_table[100001] = { 0, };
				int len = 0; //방문 길이.
				int prev = info[i];

				check[i] = len++;
				table[i] = 1; //방문했다.
				check_table[i] = 1;

				for (;;) {
					if (table[prev] == 1 && check_table[prev] == 0)
						break; //이미 방문했는데 사이클은 아니다.

					if (check_table[prev] == 1) {// 이미 방문한곳 == 사이클이다.
						cnt += len - check[prev];
						break;
					}
					check_table[prev] = 1;
					table[prev] = 1; //방문했다.
					check[prev] = len++;
					prev = info[prev];
				}
			}
		}
		printf("%d\n", N - cnt);
	}

	return 0;
}

k5nen 5년 전 0

21번 줄이 실행될 때마다 10만여개의 배열 공간을 모두 0으로 덮어씌우는 작업이 필요할겁니다. 즉,

100000

1 2 3 ... 99999 100000

과 같은 입력이 들어오면 10만 칸의 배열을 0으로 씌우는 작업을 10만번 반복할 것 같습니다.

for문 밖에서 단 하나의 (bool 대신 int로 이루어진) check_table을 선언하고, for문 안에서 매번 초기화하지 않아도 처리할 수 있는 방법을 떠올려 보세요.

k5nen 5년 전 0

위에 쓴 추측은 확실하진 않습니다. 아닐 수도 있을 것 같아요.

check_table을 for문 밖에 한번만 선언하고 풀 수 있다는 점만 참고해 주세요.

dladydwo123 5년 전 0

이미 조사한 노드에 대해 재방문 가능성이 있었습니다.

이 부분을 해결해주었고 결국 맞았습니다.

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

문제

문제

출처

ICPC

시간초과가 발생하는 이유가 무엇인지 모르겠습니다.

dladydwo123 5년 전 0

k5nen 5년 전 0

k5nen 5년 전 0

dladydwo123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말