글 읽기 - 메모리 초과 이해가 되지않습니다..

kokoxg2 6년 전 0

메모리가 128MB인데.. 선언한건 배열 2개와 벡터..

심지어 함수도 사용하지않는데..........그리고 for문이 무한 루프에 빠지는 경우도 없을텐데.......

잘 이해가 되지 않습니다.

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

std::vector<int> cycle;
int arr[105], n;
bool isVisit[105];

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) {
		scanf("%d", &arr[i]);
		if (arr[i] == i) {
			cycle.push_back(i); // 자기 자신과 사이클인 경우
			isVisit[i] = true;
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (isVisit[i] == 0) {
			int idx = i;
			// dfs 부분
			for (;; idx = arr[idx]) {
				if (isVisit[idx]) break;
				isVisit[idx] = true;
			}
            // idx 가 사이클의 시작 노드
			// 셀프 사이클 패스, 다른 사이클에 포함 안되는 경우 패스
			if (idx == arr[i]) continue;
			// 벡터에 입력
            // idx 다음 노드부터 사이클에 포함된 노드를 사이클에 넣는다.
			for (int t = arr[idx];; t = arr[t]) {
				cycle.push_back(t);
				if (t == idx) break;
			}
		}
	}

	int len = cycle.size();

	std::sort(cycle.begin(), cycle.end());
	
	printf("%d\n",len);
	for (int i = 0; i < len; ++i)
		printf("%d\n", cycle[i]);

	return 0;
}

chogahui05 6년 전 1

dfs 과정에서 무한루프가 도는 모양이네요.

이걸 제일 조심해야 하죠..

이 문제는 텀 프로젝트 (9466번)과 같은 그래프 구조를 가집니다.

그렇기 때문에, 위상정렬 스킬을 쓰셔도

사이클을 detect 하실 수 있습니다.

kokoxg2 6년 전 0

감사합니다 알려주신대로 다시한번 해보겠습니다 ~_~

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

문제

문제

출처

ICPC

메모리 초과 이해가 되지않습니다..

kokoxg2 6년 전 0

chogahui05 6년 전 1

kokoxg2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말