[Softeer] Softeer 출퇴근길 c++

 

DFS, 인접행렬, 역행렬을 사용하는 문제이다.

Candidate | Softeer Assessment UI

• S -> T로 가는 경로가 존재해야 하고,
• T -> S로 돌아오는 경로가 존재해야 한다.
• fromS와 fromT만 사용하면 S -> T와 T -> S 경로를 독립적으로 찾게 되며, 이는 각각의 경로가 서로 다른 노드를 포함할 수 있다. 예를 들어, S -> T 경로가 포함하는 노드가 T -> S 경로와 일치하지 않을 수 있다. 그래서 역행렬이 알고리즘이 필요하다.

 

• fromS: S에서 출발하여 도달할 수 있는 모든 노드.
• fromT: T에서 출발하여 도달할 수 있는 모든 노드.
• toS: S로 도달할 수 있는 모든 노드 (역방향 그래프).
• toT: T로 도달할 수 있는 모든 노드 (역방향 그래프).

fromS[i], fromT[i], toS[i], toT[i]가 모두 true인 노드 i는 S -> T -> S 경로에 포함된다.

 

따라서 4개의 dfs문을 돌려야한다.

#include<iostream>
#include<vector>

using namespace std;

int n, m, S, T;

vector<vector<int>> edge;
vector<vector<int>> redge;

vector<bool> fromS, fromT, toS, toT;

void dfs(int now, vector<vector<int>> &v, vector<bool> &visited){
    if (visited[now]) return;
    visited[now] = true;

    for(int i = 0; i < v[now].size(); i++){
        dfs(v[now][i], v, visited);
    }
    return;
}

int main(int argc, char** argv)
{
    iostream::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    edge.resize(n+1);
    redge.resize(n+1);

    fromS.resize(n+1);
    fromT.resize(n+1);
    toS.resize(n+1);
    toT.resize(n+1);
    
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        redge[y].push_back(x);
    }
    cin >> S >> T;

    // 순방향 그래프에서 S와 T에서 시작하는 DFS
    dfs(S, edge, fromS);
    dfs(T, edge, fromT);

    // 역방향 그래프에서 S와 T로 도달 가능한 노드 찾기
    dfs(S, redge, toS);
    dfs(T, redge, toT);

    int res = 0;
    for(int i = 1; i <= n; i++){
        if (fromS[i] && fromT[i] && toS[i] && toT[i]) res++;
    }
    cout << res - 2;  // S와 T 자신을 제외하려면 -2
    
   return 0;
}