글 읽기 - 런타임 에러 발생 원인 좀 도와주실수 있나요 ..?

muk0920 4년 전 0

안녕하세요.

DFS 를 이용하여 신뢰로 연결된 노드들의 갯수를 카운트하여, DFS 이후 카운트 값이 최대값일 경우 result 라는 초기화함과 동시에 벡터에 추가해주었고, 만약 최대값과 같은 갯수일 경우에는 result 에 추가만 해주며 문제를 접근했습니다.

테스트 케이스는 잘 나오는데, 1퍼에서 바로 런타임 에러가 발생합니다.

혹시 그 이유 좀 알려주실 분 계신가요 ...?

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

int N, M; 

bool check[10001];
vector<int> result;
vector<int> com[10001];
int cnt = 0;

void DFS(int idx) {

	for (int i = 0; i < com[idx].size(); i++) {
		if (!check[com[idx][i]]) {
			check[com[idx][i]] = true;
			cnt++;
			DFS(com[idx][i]);
			check[com[idx][i]] = false; 
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	int max_cnt = -10000;

	for (int i = 0; i < M; i++) {
		int st, ed; 
		cin >> st >> ed; 
		com[ed].push_back(st);
	} // 데이터 삽입 

	for (int i = 1; i <= N; i++) {
		if (!com[i].empty()) {
			check[i] = true;
			cnt = 0;
			DFS(i);
			if (max_cnt <= cnt) {
				if (max_cnt == cnt) {
					result.push_back(i);
				}
				else {
					max_cnt = cnt;
					result.clear();
					result.push_back(i);
				}
			}
			check[i] = false;
		}
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";
	cout << "\n";

}

muk0920 4년 전 0

위의 코드에서 check[i] = false 부분을 지우고 , DFS 를 시작할 때 check 를 아예 초기화 하고 진행하니 문제가 해결되는데.. 혹시 어떠한 이유에서 그런지 설명해주실분 계신가요 ..?

112224 4년 전 1

직접 확인한 것은 아니지만 int 형 범위 초과일 것으로 추정됩니다. 문제가 해결되셨다고 하니 23번과 59번을 수정하셨을 것 같은데

위의 코드의 경우

3 3

3 1

2 1

3 2

에서 idx=1일때 cnt 값이 2가 아닌 3이 나옵니다. 방문표시가 제대로 이루어지지 않아 한 정점이 여러번 카운트 되는 경우가 생기는데요. 이런 경우로 인해 cnt의 값이 초과됩니다.

long long cnt로 바꾸어서 제출한 결과 TLE가 나오는 것으로 보아 이 문제가 맞는것 같아요!

muk0920 4년 전 0

정말 감사합니다 !!

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

문제

문제

출처

ICPC

런타임 에러 발생 원인 좀 도와주실수 있나요 ..?

muk0920 4년 전 0

muk0920 4년 전 0

112224 4년 전 1

muk0920 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말