[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인 정점의 개수를 정답이라고 출력했다.

 

 

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

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

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

 

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

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

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

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

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

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

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