[ 소프티어 ] 출퇴근길 (C++)

https://softeer.ai/practice/6248

 출근길에 들른 동네를 퇴근길에 다시 지날 수 있는 경우는, S에서 T로 가는 경로와 T에서 S로 가는 경로 모두에 포함되는 경우이다.

따라서 S에서 T로 가는 경로와, T에서 S로 가는 경로를 모두 탐색하여 두 경로에 모두 속한 정점의 개수를 찾으면 된다.

 

[ 풀이 방법 ]

1. DFS를 이용해 S -> T, T -> S로의 경로를 탐색

  - DFS의 반환값을 이용해 목적지에 도달 가능한지(경로에 포함되는지)를 체크

    - 목적지에 도달하지 못하고 DFS가 종료된다면 false를 return

    - 목적지에 도달한다면 true를 반환하고 DFS를 종료

 - true가 반환된 경로에 존재하는 정점들만 체크

 

2. S -> T, T -> S 경로 탐색에서 모두체크된 정점의 개수를 출력

 

그러나 이렇게 구현할 경우 각 정점을 방문하는 순서에 따라 목적지까지 도달할 수 있는 경로가 있음에도 체크하지 못하는 경우가 발생한다.

Ex) 목적지에 도달할 수 있는 경로에 포함되는 정점이 이미 visited 처리되어 방문할 수 없는 경우

 

 위 경우를 해결하기 위해 visited된 정점으로의 경로가 있는 경우 true를 return하기에는 아직 해당 경로가 목적지에 도달할 수 있는지 알 수 없다.

 

 따라서 다른 접근 방법이 필요하다.

 문제는 "시작점에서 목적지까지 경로가 존재하는가"가 아닌, "시작점에서 목적지까지 가는 경로에 어떤 정점이 포함되는가"이기 때문에,

"시작점에서 특정 노드로 갈 수 있는가" + "특정 노드에서 목적지로 갈 수 있는가"를 확인하여 S -> T, T  -> S에 대해 두 조건을 만족한다면 해당 노드는 출근길에 들른 동네를 퇴근길에 다시 지날 수 있는 경우에 해당한다고 볼 수 있을 것이다.

 

 즉,

"시작점에서 특정 노드로 갈 수 있는가"

1. S에서 특정 노드로 갈 수 있는 경로가 존재하는가?

2. T에서 특정 노드로 갈 수 있는 경로가 존재하는가?

 

"특정 노드에서 목적지로 갈 수 있는가"

3. 특정 노드에서 T로 갈 수 있는 경로가 존재하는가?

4. 특정 노드에서 S로 갈 수 있는 경로가 존재하는가?

를 모두 만족하는 node를 모두 찾으면 문제를 해결할 수 있고, 

 

주어진 단방향 그래프와 DFS를 이용해 S, T에서 시작하여 도달할 수 있는 모든 노드를 찾고(1, 2),

주어진 단방향 그래프의 역방향 그래프를 만들고 DFS를 이용해 S, T에서 시작하여 도달할 수 있는 모든 노드를 찾도록(3, 4) 구현한다면 

모든 노드를 최대 4번 방문하고 모든 경로를 최대 4번 탐색하기 때문에 O(n + m)의 시간복잡도를 가질 것이다.

 

 이 때, 1번과 2번에 해당하는 경로를 탐색할 때에는 도착점에 도달하면 DFS가 종료되도록 구현해야 하고, 3번과 4번에 해당하는 경로를 탐색할 때에는 해당 조건을 무시해도 된다.

 

[ 회고 ]

 처음에 DFS가 아닌 BFS를 이용하여 S -> T, T -> S로의 경로 탐색을 구현하였고, 목적지에 도달한 경우에만 방문한 정점을 체크하는 기능을 구현하는데 길고 복잡한 코드들이 필요해 구현에 시간이 많이 걸렸고 디버깅도 쉽지 않았다.

-> 그래프 탐색 문제를 풀 때, DFS와 BFS 중 어느 알고리즘이 더 적합한지 생각해야 할 것이다.

 

 또한 쉬운 문제라고 생각하고 구현 계획을 확실히 생각하지 않아, 각 정점을 방문하는 순서에 따라 목적지까지 도달할 수 있는 경로가 있음에도 체크하지 못하는 경우가 발생할 수 있다는 것을 미리 생각하지 못했다.

 

 결국 다른 사람의 코드를 보고 풀었고, 그럼에도 문제를 급하게 읽고 접근 방법과 구현 계획을 대충 생각하고 구현하다보니 놓친 조건들이 많아 구현했던 코드가 왜 틀렸는지^[각주:1] 이해하는데 시간이 오래 걸렸다.

 

 따라서, 구현 문제가 아니더라도 정확한 접근 방법과 구현 계획을 세운 뒤 구현 단계에 들어가도록 연습이 필요할 것이고, 구현, 시뮬레이션 문제 뿐 아니라 다양한 문제를 연습하도록 해야할 것이다.

 

[ 정답 코드 ]

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, M;
int S, T;

vector<vector<int>> edge;
vector<vector<int>> reverseEdge;
vector<vector<bool>> path;

void dfs(int u, const vector<vector<int>>& edge, int pathNum) {

    if(pathNum == 0 && u == T) return;
    if(pathNum == 1 && u == S) return;
    if(path[pathNum][u]) return;
    else path[pathNum][u] = true;
    
    for(int i = 0; i < edge[u].size(); i++) {
        dfs(edge[u][i], edge, pathNum);
    }
}

int main(int argc, char** argv)
{
    iostream::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    edge.resize(N+1);
    reverseEdge.resize(N+1);
    path.resize(4, vector<bool>(N+1));
    
    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        reverseEdge[v].push_back(u);
    }
    cin >> S >> T;

    dfs(S, edge, 0);
    dfs(T, edge, 1);

    dfs(T, reverseEdge, 2);
    dfs(S, reverseEdge, 3);
    
    int res = 0;
    for(int i = 1; i <= N; i++) {
        if(i == S || i == T) continue;
        bool flag = true;
        for(int j = 0; j < 4; j++) {
            if(!path[j][i]) flag = false;
        }
        if(flag) res++;
    }
    cout << res << '\n';
    
   return 0;
}​

1. 1번과 2번에 해당하는 경로를 탐색할 때에는 도착점에 도달하면 DFS가 종료되도록 구현해야 하고, 3번과 4번에 해당하는 경로를 탐색할 때에는 해당 조건을 무시해도 된다. [본문으로]