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

제가 푼 방식은 정점이 n번까지 다다르면 카운트를 하나 올리고 방문여부를 체크하던 배열을 원상태로 초기화하는 방법입니다.

근데 이게 m이 작을 때는 잘 작동하는데 m이 커지는 순간 스택 오버플로우가 발생합니다..! 손그림 그려서 해봤는데 스택 오버플로우가 발생할 것 같기도 하고 왜 발생하는 건가 싶기도 해서 질문드립니다...(너무 긴가민가해서 좀 더 명쾌한 이유를 알고 싶어서요 ㅠㅠ)

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<string>

int n, m;  // 정점 n개, 간선 m개
vector<vector<int>> adjacent;  // -1은 연결 없음
vector<int> visited;
int ans = 0;

void DFS(int pre)  
{
	if (pre >= n)  // n에 다다르면 카운트 증가, 방문 배열 초기화
	{
		ans++;
		visited.clear();
		visited.resize(n + 1, 0);
		return;
	}

	visited[pre] = 1;  // 일단 방문했으니 체크

	for (int i = 1; i <= n; i++)
	{
                // 방문한 적 있거나 연결 끊겨있으면 continue해서 무시
		if (visited[i] == 1 || adjacent[pre][i] == -1)
			continue;
		DFS(i);  // 그 외라면 DFS 재귀호출
	}
}

int main(void)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	freopen("input.txt", "rt", stdin);  // 파일 입력받음

	cin >> n >> m;

	adjacent.resize(n + 1, vector<int>(n + 1, -1));
	for (int i = 0; i < m; i++)
	{
		int s, e;  // 시작 정점, 도착 정점
		cin >> s >> e;
		adjacent[s][e] = 1;
	}
	visited.resize(n + 1, 0);

	DFS(1);
	cout << ans;
}

아 그런데 스택 오버플로우 생기는 것 땜에 강사님 설명 봤고, 설명을 통해 고친 내용은 완벽히 이해된 상태입니다! 그냥 스택 오버플로우 발생 이유를 정확히 알고 싶어 질문드립니다 감사합니다