boj 4803번 문제에서 메모리 초과에 관하여. 그리고 내 맥북에서 segmentation falut

 

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

int n, m, tc, Trees;
vector<int> adj[505];
bool vis[505];
bool isTree;

void dfs(int cur, int prev){
    // vis[cur]=true;
    // isTree=true;
    for(auto nxt: adj[cur]){
        if(nxt==prev) continue; //부모는 제외.
        if(vis[nxt]){
            isTree=false;
            continue;
        }
        // vis[nxt]=true;//이거 한줄 안했다고 메모리 초과가 난다고? 분석해보자.
        /*정상적인 코드는 vis[nxt]=true 의 주석을 해제해야 한다*/
        dfs(nxt,cur);
    }
} 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    while(true){
        cin>>n>>m;
        if(n==0 && m==0) break;
        fill(vis,vis+n+1,0);
        
        for(int i=1; i<=n; i++){
            adj[i].clear();
        }
        
        while(m--){
            int u, v;
            cin>>u>>v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        Trees=0;
        for(int i=1; i<=n; i++){
            if(vis[i]) continue;
            vis[i]=true;
            isTree=true;
            dfs(i,-1);
            Trees+=isTree;
        }
        cout<<"Case "<<++tc<<": ";
        if(Trees==1) cout<<"There is one tree."<<'\n';
        else if(Trees>1) cout<<"A forest of "<<Trees<<" trees."<<'\n';
        else cout<<"No trees."<<'\n';
    }
}

처음에 이런 코드를 제출하였는데 백준에서 메모리 초과를 받게 되었다. 아무리 생각해봐도 메모리가 초과할 영역이 재귀함수를 호출할때 재귀가 깊어지는 경우에 발생하는 경우밖에 없었는데, 이때에 백준의 경우 스택 메모리 제한이 없기 때문에 재귀함수 깊이가 엄청 깊지 않은이상은 이러한 문제가 발생하지 않을 것이라는 생각이 들었다. 256 이라는 메모리 용량을 넘어설정도로 깊이가 계속 깊어져서 메모리 초과가 발생한다고 생각되었고, 코드를 이리저리 보고 다른 코드와 비교해보니

재귀함수 내에서 vis[nxt]가 있어야 할 위치에 이 부분을 두지 않았다는걸 알게 되었다. 

근데 예제를 돌려보면 정상적으로 결과물을 출력해서 저 코드를 정상적인 위치에 두지 않았다는것도 파악하지 못했다. 

왜 예제 코드의 경우는 정상적으로 출력이 되고, 제출을 하면 스택메모리 영역이 커지면서 메모리 초과가 발생하는지에 대해서 생각해보다 보니, 

예제로 주어진 사이클이 있는 예제가, 1  -> 2 ->  3 -다시->1 형태처럼, 처음 시작하는 위치에 사이클이 달린 경우들을 예제로 주는걸 알 수 있었다. 

이때에 처음 위치의 경우는 재귀함수 dfs 내에 체크하는 부분이 없지만, dfs를 감싸고 있는 for문 내부에서 첫번째 시작점의 경우 체크를 해주기 때문에 이렇게 체크되어있는 첫번째 vertex를 만나면 재귀함수가 더 깊어지지 않고 종료되는 것이다. 

 

그래서 내가 예제입력을 1->  (2 3 4)(사이클) 형태로 

4 4

1 2

2 3

3 4

4 2

 

를 제출하니, 내 맥에서 

zsh: segmentation fault 오류메시지를 출력하면서

정상적으로 코드가 동작하지 않는걸 확인할 수 있었다. 

 

이처럼 주어진 예제가 통과한다고 코드를 잘 작성했다는 보장이 없다. 

그리고 재귀 내에서 nxt 원소들에 대해서 제대로 vis를 true로 바꾸어 주는걸 명심하도록 하자. 

그리고 이런식으로 메모리 초과가 깊어지면, dfs로 프로그램을 작성시에 분명 dfs 영역에서 무언가 문제가 발생해서

스택 메모리 영역에서 메모리 초과가 발생할 수 있다는것을 알고 문제를 해결해보도록 하자.