인프런 커뮤니티 질문&답변

http://boj.kr/b85b560b22f84a49afb83d72cb2269c9

이렇게 했는데, 왜 런타임 에러가 발생할까요..??

안녕하세요 kim님 정말 잘 짜셨네요 ㅎㅎ

kim님 코드 중에 이것만 수정해서 제출해보실까요?

vector<int>visit_ok[10001];

다음과 같이 맞았다고 뜰껍니다.

http://boj.kr/91d4b35ef96a47b384598b5c8cc4ab3f

이 문제의 범위를 보면 10000번이 나타날 수 있기 때문에 배열의 범위를 10001 이상으로 잡으셔야 합니다.

• N은 10,000보다 작거나 같은 자연수

• 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

이게 사실 자주 실수하는 부분인데 이 부분에 관한 내용은 교안에도 있는데요.

배열의 범위는 항상 +1, +4정도 좀 더 넓게 잡으시는게 맞왜틀에서 빠져나올 수 있어요. (교안 다시 참고 부탁드려요)

나머지 코드는 완벽합니다.

설 잘보내세요 ㅎㅎ

감사합니다.

교안에서 글로 보다가 이렇게 경험해보니, 새롭네요.. ㅎㅎ

설명 너무 감사하고, 계속해서 열심히 해보겠습니다! 강사님도 즐거운 명절 되세요!!

음.. 이 문제를 왜 visited 없이 풀 수 있다고 생각하시나요?

시간초과 말구요. visited없이 하면 무한루프 발생할텐데요.

제가 디버깅코드를 좀 작성해봤거든요. 참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b;
vector<int>visit_ok[10000];
int  cnt;
//map<int, int>mm;
vector<pair<int, int>> v;

void dfs(int here)
{
	cout << "HERE : " << here << '\n'; 
	for (int i : visit_ok[here])
	{
		if (i >= 1)
		{
			dfs(i);	cnt++;
		}
	}
}
	
bool cmp(pair<int, int>a, pair<int, int>b)		// 정렬공부 다시해야함.  필수!
{
	if (a.second == b.second)	return a.first < b.first;
	// < 면, 오름차순 ||  > 면, 내림차순

	return a.second > b.second;
}

int main(void)
{
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		visit_ok[b].push_back(a);
		// 이러면 b의 것이 갈 수 있는 곳들이 뜨겠지.
	}

	for (int i = 1; i <= n; i++)
	{
		cnt = 0;
		dfs(i);
		v.push_back({ i,cnt });
	}

	sort(v.begin(), v.end(), cmp);
	
	int _max = -1;
	for (int i = 1; i <= n; i++)
	{
		_max = max(_max, v[i].second);
	}

	//for (int i = 0; i < v.size(); i++)
	//{
	//	cout << v[i].first << ' ';
	//}
	
	for(int i = 0 ; i < v.size() ; i++)
	{ 
		if (_max == v[i].second)
		{
			cout << v[i].first << ' ';
		}
		else break;
	}
	
}

TC는 다음과 같습니다.

5 2

3 1

1 3

감사합니다.

visited 없이 해결할 수 있다 생각한 이유는..

3이 1을 신뢰하고, 4가 3을 신뢰하는 경우, dfs(1)을 할 때, 1 -> 3 -> 4 로 가고, cnt++로 해줘서 갯수를 파악할 수 있다고 생각해서였습니다. 여러 개가 있는 경우, 그 모든 걸 어차피 방문해야하는데 라는 생각이 들어서 visited를 사용하지 않은 것 같습니다. 이렇게 상호 신뢰 관계는 생각지 못한 것 같네요. 명쾌한 답변 감사합니다! 좀 더 고민해보겠습니다~