백준 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 (C++)

https://www.acmicpc.net/problem/24479

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

---

Solved By: DFS

 

DFS 코드 구현의 재발견을 한 듯한 문제였습니다. 이번에 배우게 된 코드는 DFS와 백트래킹의 구현 방식에 있어서 경계를 짓는? 듯한 느낌이 들었습니다.

 

기존 DFS 방식

void dfs(int node){
    //cout << node << ' ';
    if(!visitedOrder[node]) visitedOrder[node] = ++order;
    for(int i = 0; i < adj[node].size(); i++){
        int next =  adj[node][i];
        
        if(!visited[next]){
            visited[next] = true;
            dfs(next);
            visited[next] = false;
        }
    }
}

새로운 DFS 방식 (main에서 굳이 시작 노드 visited 처리 안 해줘도 됨.)

void dfs(int node){
    if(!visited[node]){
        visited[node] = true;
        visitedOrder[node] = ++order;
    }
    
    //cout << "pass: " << node << '\n';
    
    for(int i = 0; i < adj[node].size(); i++){
        int next = adj[node][i];
        dfs(next);
    }
}

사실 원래 DFS에서 visited를 False로 안 바꿔주면 해결되는 문제임(하단 DFS 참고)

(이 DFS로 제출하면 통과함)

즉, visited를 False로 다시 풀어줄 필요가 없다는 뜻임.

void dfs(int node){
    //cout << node << ' ';
    if(!visitedOrder[node]) visitedOrder[node] = ++order;
    for(int i = 0; i < adj[node].size(); i++){
        int next =  adj[node][i];
        
        if(!visited[next]){
            visited[next] = true;
            dfs(next);
        }
    }
}

 

아직도 Recursive Call을 완전히 마스터하지는 못 한 거 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;

vector<int> adj[MAX];
int visitedOrder[MAX];
bool visited[MAX];
int n, m, r;
int order = 0;

void dfs(int node){
    if(!visited[node]){
        visited[node] = true;
        visitedOrder[node] = ++order;
    }
    
    //cout << "pass: " << node << '\n';
    
    for(int i = 0; i < adj[node].size(); i++){
        int next = adj[node][i];
        dfs(next);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m >> r;
    for(int i = 0; i < m; i++){
        int v, u; cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    
    // O(N^2logN)
    for(int i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end());
    
    dfs(r);
    
    for(int i = 1; i <= n; i++){
        cout << visitedOrder[i] << '\n';
    }
    
    return 0;
}