[Algorithm] Softeer :: 출퇴근길

https://softeer.ai/practice/6248

Softeer - 현대자동차그룹 SW인재확보플랫폼

 
 
using namespace std;
 
 
int n, m, a, b, s, t;
vector<vector<int>> graph(100001);
vector<vector<int>> reverseGraph(100001);
bool visited[100001] = { false };
int visitedCount[100001] = { 0 };
int answer = 0;
 
 
void DFS(int node, int target, vector<vector<int>>& p_Graph)
{
    for (int i = 0; i < p_Graph[node].size(); ++i)
    {
        int nextNode = p_Graph[node][i];
 
        if (visited[nextNode]) continue;
        if (nextNode == target) continue;
 
        visited[nextNode] = true;
        ++visitedCount[nextNode];
        if (visitedCount[nextNode] == 4) ++answer;
 
        DFS(nextNode, target, p_Graph);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
 
        graph[a].push_back(b);
        reverseGraph[b].push_back(a);
    }
 
    cin >> s >> t;
 
    memset(visited, false, sizeof(visited));
    visited[s] = visited[t] = true;
    DFS(s, t, graph); // s에서 찾아갈 수 있는 모든정점 체크.
 
    memset(visited, false, sizeof(visited));
    visited[t] = true;
    DFS(t, -1, reverseGraph); // t로 갈 수 있는 모든정점 체크.
 
    memset(visited, false, sizeof(visited));
    visited[s] = visited[t] = true;
    DFS(t, s, graph); // t에서 찾아갈 수 있는 모든정점 체크.
 
    memset(visited, false, sizeof(visited));
    visited[s] = true;
    DFS(s, -1, reverseGraph); // s로 갈 수 있는 모든 정점 체크.
 
    cout << answer;
}
 
 
 

 

역간선 그래프에 대해 알고 있어야 했던 문제.

일단 문제에서 구해야할 것은 출근길의 경로와 퇴근길의 경로에 속해있는 모든 정점의 개수를 구하는 문제이다.

그냥 단순하게 생각하면 각 정점마다 s,t에 대해서 탐색을 하면 해결할 수 있겠지만, 당연히 시간이 많이 걸린다.

 

그러면 최소의 탐색으로 문제를 해결할 수 있는 방법을 찾아보자. 

먼저 크게 두단계로 나눈다.

 

1. s에서 t로 갈 수 있는 모든 정점을 구하고,

2. t에서 s로 갈 수 있는 모든 정점을 구한 후, 공통된 정점의 개수를 구해보자.

 

 

1-1. 먼저 s를 기준으로 최종목적지를 t로하는 탐색을 수행해서 탐색한 모든 정점을 체크한다.

       최종목적지를 t로한다는 것은, t에 도착한 이후엔 다른곳으로 뻗어나가면 안된다는 것이다.

        출근경로에는 t가 반드시 한번만 등장해야한다는 조건 때문이다.

 

1-2. 그다음 t로 갈 수 있는 모든 정점을 찾아보자.

        보통은 모든 정점에 대해서 탐색해야 알 것 같지만, 역간선그래프를 이용하면 한번의 탐색으로 가능하다.

        처음에 m개만큼의 간선정보를 입력할 때, 역간선용 그래프변수를 따로 선언해서 간선의 정보를 역으로 입력받아놓는다. 이 역간선그래프에다가 시작지점 t를 넣어놓고 탐색을 수행했을 때 만나는 모든 정점은 't로 갈 수 있는' 정점이다.

        

 

이 1-1과 1-2, 총 2번의 탐색을 했을 때 공통적으로 탐색되어진 정점은 s에서 t로 갈 수 있는 정점이 보장되어진다.

이렇게 t에서 s로 가는것도 똑같이 구하면 된다.

내 코드같은 경우, 결국 총 4번의 DFS를 하기때문에 매번 DFS할때마다 방문체크된 정점을 카운팅해서 카운팅값이 4인 정점의 개수를 정답이라고 출력했다.

 

즉, 출근길에도 있어야하고, 퇴근길에도 있어야하고, 해당정점에서 출발했을 때 출발지랑 목적지에 갈 수 있어야 한다.

여기까지 왔는데도 '왜 4번 검사해야하지? 걍 2번만 하면되지않나?'라는 의문이 든다면, InDegree만 있고 OutDegree는 없는 정점이 있다고 상상해보면 된다.

그럴 경우, 출발지나 목적지에서 이 정점을 방문할 수 있더라도 이 정점에서는 출발지랑 도착지를 갈 수 없다.

그렇기 때문에 두번만 체크하면 안된다.

 

 

근데 여기서 중요한점이 하나 있다.

기본 간선그래프로 탐색을 수행할 때는 시작지점뿐만 아니라, 목적지에도 방문체크해서 도달 못하게 막아놔야 한다.

출근길이라면 회사가 단 한번만 등장해야하고, 퇴근길이라면 집이 단 한번만 등장해야 하기 때문이다.

뭐 문제설명에는 출발지->도착지이동할 때는 출발지는 얼마든지 재방문해도 된다고하는데, 어차피 출발지부터 완탐으로 뻗어나가는거라서 있으나마나한 설명이다. 도착지 -> 출발지 또한 마찬가지.

 

단, 역간선그래프로 탐색을 수행할 때는 시작지점'만' 방문체크해야 한다. 

예를들어 t로 갈 수 있는 모든 정점을 구핸다했을 때, 역간선그래프로 시작지점을 t로하고 탐색을 수행할 것이다.

이 때, 수행 전에 s에 방문처리를 해놓으면 안된다. 

왜냐하면 t로 갈 수 있는 경로중에는 s를 거쳐야만 갈 수 있는 경로가 존재할 수 있기 때문이다.

그래서 이 문제에서 역간선그래프탐색을 할 때는 탐색시작지점만 방문체크하고 탐색해야 한다.

이거 때문에 시간을 좀 소모했다.

참고 테스트케이스로는, 이 문제 예시1번 테스트케이스에다가 (시작 1,도착 3인 테스트케이스) 1->6, 6->1 간선 두개를 추가해보면 된다. 바로 이해된다.