글 읽기 - DFS 효율적인 코딩 방식에 대해서 궁금합니다

dreamian 6년 전 0

DFS로 코딩할 때 chk(방문을 했는지 안 했는지 가리키기 위한 bool type 배열)을 어떻게 처리하시나요?

문제를 풀 때마다 이 부분이 자꾸 걸립니다.

저 같은 경우에는 DFS를 돌릴 때,

chk(true) -> 다음 원소에 대한 탐색(DFS) -> chk(false)

이런 식으로 초기화를 해나가는데, 코드가 길어지거나 문제가 복잡할 경우 디버깅할 때 애를 많이 먹어 여쭙니다.

memcpy를 이용해서 복사하는 방식으로 해야하는 건지에 대해도 생각해봤는데 오히려 더 비효율적일 것 같고,

단순히 한 경로로만 쭉 DFS를 돌리는 거라면 상관이 없지만 모든 노드에 대한 DFS를 처리해야하는 경우에는 어떻게 하면 좋을까요?

아래 소스코드에서 제가 뻘짓한 것을 주석 '//'으로 처리해놓았는데, 혹시 조언을 주시면 정말 감사하겠습니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
#define mp make_pair
#define vpii vector< pair<int,int> >
#define node(a,i) vertex[a][i].first
#define dist(a,i) vertex[a][i].second

int ans=0;
int cmp=0;
int temp;

void DFS(vector< vpii > &vertex,int a,vector<bool> &chk){
    if(ans<cmp){
        ans=cmp;
        temp=a;
    }

    int sz=vertex[a].size();
    for(int i=0;i<sz;i++){
        if(!chk[node(a,i)]){
            chk[node(a,i)]=true;
            cmp+=dist(a,i);
            DFS(vertex,node(a,i),chk);
            //cmp-=dist(a,i);
            //chk[node(a,i)]=false;
        }
    }
}

int main(){
    int v;
    scanf("%d",&v);
    vector< vpii > vertex(v+1,vpii(0));
    vector<bool> chk(v+1,false);
    queue <int> que;

    for(int i=1;i<=v;i++){
        int v_;
        scanf("%d",&v_);
        while(1){
            int pt;
            scanf("%d",&pt);
            if(pt==-1) break;
            else {
                int dist;
                scanf("%d",&dist);
                vertex[v_].push_back(mp(pt,dist));
            }
        }
        if(vertex[v_].size()==1) que.push(i);
    }
    
    //chk[1]=true;
    DFS(vertex,1,chk);
    //chk[1]=false;
    //chk[temp]=true;
    //ans=0; cmp=0;
    DFS(vertex,temp,chk);
    
    printf("%d\n",ans);
}

tjrwodnjs999 6년 전 2

저같은 경우에는 visit배열을 하나 만든다음에 배열 크기를 노드의 수만큼 선언해 준 뒤에 DFS를 새로 시작할 때마다 fill로 visit배열을 초기화 시켜 줍니다.

dreamian 6년 전 1

답변 정말 감사합니다.

memset보다 fill을 적용하는 게 훨씬 효율적일 것 같아요 ㅎㅎ

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

문제

문제

출처

ICPC

DFS 효율적인 코딩 방식에 대해서 궁금합니다

dreamian 6년 전 0

tjrwodnjs999 6년 전 2

dreamian 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말