boj 1325번 문제를 통해 바라보는, 노드에 붙어있는 노드들의 총 갯수를 구하는 방법에 대한 정방향 dfs와 역방향 dfs 풀이법 차이.

일단 내가 처음에 풀이한 방법으로는 시간초과가 발생하여서 참고 코드를 보았는데, 

이 코드에서는 역방향으로 제시되어 있는 입력을 그대로 역방향으로 받아들여서 dfs를 도는 형태의 코드를 작성하였다. 

이렇게 되면 결국 역방향으로 가는 형태로 해석하면서 맨 마지막에 도달할때 +1을 해주는 식으로 그 해당 노드에서의 총 연결 노드들의 갯수가 쌓이는 식이었는데, 아주 훌륭한 풀이라고 생각된다. 

 

/*역방향으로 설정해서 돌리는 dfs*/
#include <bits/stdc++.h>
using namespace std;

int mx;
int score[10'005];
vector<int> adj[10'005];
bool vis[10'005];

void dfs(int st){
    vis[st]=1;
    score[st]++;
    mx=max(mx,score[st]);
    for(int nxt:adj[st]){
        if(vis[nxt]) continue;
        dfs(nxt);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin>>n>>m;
    while(m--){
        int u, v;
        cin>>u>>v;
        adj[u].push_back(v);
    }
    // fill(score,score+10'005,0);
    for(int i=1; i<=n; i++){
        fill(vis,vis+10'005,0);
        dfs(i);
    }
    for(int i=1; i<=n; i++)
        if(score[i]==mx) cout<<i<<' ';
}

 

그런데 내가 예제 입력을 반대로 받아서 다시 정방향으로 바꾸어서 dfs를 돌리는 풀이를 작성해보았는데, 뭔가 신경써야 할 부분도 많고, 그리고 역방향으로 입력받아서 푸는 풀이에 비해서 풀이도 조금 더 길어지고 까다로워 지는듯한 느낌을 받았다. 

 

/*정방향 dfs*/
#include <bits/stdc++.h>
using namespace std;

int mx;
int n, m;
vector<int> adj[10'005];
int score[10'005];
bool vis[10'005];

int score_cur[10'005];

int dfs(int cur){
    vis[cur]=true;
    score[cur]++;
    for(auto nxt: adj[cur]){
        if(vis[nxt]) continue;
        dfs(nxt);
        score[cur]+=score[nxt];
    }
    mx=max(mx,score[cur]);
    return score[cur];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    while(m--){
        int u, v;
        cin>>v>>u;
        adj[u].push_back(v);
    }
    
    for(int i=1; i<=n; i++){
        fill(vis,vis+n+1,false);
        fill(score,score+n+1,0);
        score_cur[i]=dfs(i);
    }
    for(int i=1; i<=n; i++){
        if(score_cur[i]==mx) cout<<i<<' ';
    }
}

아무래도 처음에는 역방향으로 예제입력을 주는것이 더 힘들게 만들기 위해서 트릭을 쓰는 것이라 생각했는데, 

과정을 겪어보니 그대로 역방향으로 받아서 역방향으로 dfs를 도는것이 노드들에 연결된 전체 노드의 갯수를 세는 문제에서는

역방향으로 주어지면 그대로 역방향으로 그래프를 만들어서 dfs를, 정방향으로 주어지면 내가 일부러 역방향으로 받아서 역방향 dfs를 도는것이 훨씬 쉽게 원하는 답을 얻을 수 있는 코드를 짤 수 있을것 같다. 

 

/*내가 정방향 dfs를 짤때 비효율적으로 짜서 이런 결과가 나왔을 수도 있으니 직접 효율적인 코드 작성을 시도해볼것을 권함*/