BFS/DFS 학습 중에 궁금한 점

작성한 질문수 5

0

안녕하세요 0303님 ㅎㅎ

일단 3 - C에서 visited를 걸고 있습니다.

void dfs(int y,int x,vector<pair<int,int>> &v){ 
    for(int i=0; i<4; i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(nx<0 || nx>=n || ny<0 || ny>=n || visited[ny][nx])continue;
        if(abs(a[ny][nx]- a[y][x]) >= l && abs(a[ny][nx] - a[y][x]) <= r){
            visited[ny][nx] =1;
            v.push_back({ny,nx});
            sum += a[ny][nx];
            dfs(ny,nx,v);
        }

근데 지금 보시면 ny, nx를 걸고 있는데 visited[y][x]=1 이게 왜 없냐? 라는 말씀이시죠?

dfs는 y, x로도 걸고 ny, nx로도 걸 수 있습니다.

우리가 앞서 배운 dfs 개념을 기반으로 설명하면요.

https://blog.naver.com/jhc9639/222289089015

구현방법1 : 돌다리를 두들겨 보다.

1번코드

void dfs(int here){
    visited[here] = 1; 
    for(int there : adj[here]){
        if(visited[there]) continue;
        dfs(there);
    }
}

앞의 코드는 사실 이렇게 해도 되는 코드입니다.

2번코드

void dfs(int here){ 
    for(int there : adj[here]){
        if(visited[there]) continue;
        visited[there] = 1;
        dfs(there);
    }
}

0503님께서 물어보신 차이는 다음과 같습니다.

2번코드는 시작지점에 대한 부분을 방문처리하고 해야 한다는 코드가 더 들어가야 한다는 점이 다릅니다. 예를 들어 1 2 3 4 이렇게 탐색한다 라고 했을 때

dfs를 처음 호출 할 때 2번코드는 다음과 같이 시작지점에 대한 방문처리를 하고 들어가야 하지만 1번코드는 그렇지가 않습니다.

visited[1] = 1;
dfs(1)

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.