글 읽기 - 두 코드의 차이점이 뭘까요?

tldnjs0821 1년 전 0

아래의 코드로 제출해서 맞긴 했습니다.

근데 45번째줄부터 55번째줄까지의 코드를

if(visit[next]==true && next!=pre[cur])

cycle[cur]=true;

find_cycle=true;

while(cur != next){

cycle[pre[cur]]=true;

cur=pre[cur];

}

return;

}

이렇게 바꾸면 메모리 초과라고 나오네요.

그저 if문 두번 통과하는 것을 하나로 합친 것이라 생각했는데

뭔가 다른 점이 있을까요?

알려주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

int n;
vector<int> edge[3001];
bool visit[3001];
bool cycle[3001];
int dist[3001];
int pre[3001];
bool find_cycle;

void bfs(){
    queue<pair<int, int>> q;
    for(int i=1; i<n+1; i++){
        if(cycle[i]==true){
            q.push({i, 0});
            visit[i]=true;
        }
    }
    while(!q.empty()){
        int cur=q.front().first;
        int dis=q.front().second;
        q.pop();
        visit[cur]=true;

        for(int i=0; i<edge[cur].size(); i++){
            int next=edge[cur][i];
            if(visit[next]==false){
                dist[next]=dis+1;
                q.push({next, dist[next]});
            }
        }
    }
}

void check_cycle(int cur){
    visit[cur]=true;
    for(int i=0; i<edge[cur].size(); i++){
        if(find_cycle) return;
        int next=edge[cur][i];
        if(visit[next]==true){
            if(pre[cur]!=next){
                cycle[cur]=true;
                find_cycle=true;
                while(cur != next){
                    cycle[pre[cur]]=true;
                    cur=pre[cur];
                }
                return;
            }
        }
        else{
            pre[next]=cur;
            check_cycle(next);
        }
    }
}

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

    cin >> n;
    for(int i=1; i<n+1; i++){
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    check_cycle(1);
    memset(visit, false, sizeof(bool)*3001);
    bfs();
    for(int i=1; i<n+1; i++)
        cout << dist[i] << " ";
}

adfsfsf 1년 전 0

단순히 합치는 것이 아니기 때문입니다.

56번 줄의 else는 if(visit[next]==true)에 걸린 것이지, if(pre[cur]!=next)에 걸린 것이 아닙니다.

둘을 합쳐서 if(visit[next]==true && pre[cur]!=next)가 되면 pre[cur]==next이기만 해도 else로 넘어가는 것입니다. 하지만 else로 넘어가는 것은 visit[next]!=true인 경우만이어야 하기 때문에 차이가 생기는 것입니다.

tldnjs0821 1년 전 0

그렇군요.

그래서 말씀해주신 흐름대로 else로 넘어가면 이미 방문한 곳에 대해 다시 check_cycle을 진행하니까

오류가 나오는군요.

근데 그러면 무한루프가 돌아서 시간초과같은 오류가 나올것 같은데 메모리초과가 나오는 이유가 있을까요?

adfsfsf 1년 전 0

check_next 함수 내부에 next 변수가 있는데 이게 재귀될 때마다 하나씩 추가되어서 그런 거 같네요.

adfsfsf 1년 전 0

정확히는, 함수가 재귀될 때 상위 함수에서 생성된 변수들은 사라지지 않습니다. for문의 i도 마찬가지로 재귀될 때마다 추가되겠네요.

재귀함수가 은근 오류가 잘 나서 가능하면 루프로 대체하는 걸 추천드립니다.

tldnjs0821 1년 전 0

시간초과 에러가 나기 전에 메모리초과 에러가 나는 것이겠네요.

답변감사드립니다.

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

문제

문제

출처

ICPC

두 코드의 차이점이 뭘까요?

tldnjs0821 1년 전 0

adfsfsf 1년 전 0

tldnjs0821 1년 전 0

adfsfsf 1년 전 0

adfsfsf 1년 전 0

tldnjs0821 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말