[SOFTEER] 6회 정기 코딩 인증평가 기출 - 출퇴근길 (역방향 그래프 의미 알아두기)

문제출처

• 출퇴근길

문제접근1

1. S 에서 DFS 로 방문 가능한 모든 노드를 체크한다.
2. T 에서 DFS 로 방문 가능한 모든 노드를 체크한다.
3. 모든 노드에서 DFS 를 하여 S 로 방문 가능한 노드를 체크한다.
4. 모든 노드에서 DFS 를 하여 T 로 방문 가능한 노드를 체크한다.
5. 1 ~ 4번 에 공통으로 들어가는 노드의 개수를 센다.

구현1 (시간초과)

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>

#define MAX_N 100001

using namespace std;

int n, S, T;
bool visited[MAX_N];
vector<int> graph[MAX_N];
vector<int> table[MAX_N];

void dfs(int start, int node)
{
    for(int i=0; i<graph[node].size(); i++) {
        int nextNode = graph[node][i];
        if(visited[nextNode]) continue;
        visited[nextNode] = true;
        table[start].push_back(nextNode);
        dfs(start, nextNode);
    }
}

bool getStatus(int node)
{
    if(find(table[S].begin(), table[S].end(), node) == table[S].end()) return false;
    if(find(table[T].begin(), table[T].end(), node) == table[T].end()) return false;
    return true;
}

void updateTable()
{
    memset(visited, false, sizeof(visited));
    visited[S] =true; visited[T] =true;
    dfs(S, S);
    
    memset(visited, false, sizeof(visited));
    visited[S] =true; visited[T] =true;
    dfs(T, T);

    for(auto node : table[S]) {
        memset(visited, false, sizeof(visited));
        visited[node] = true;
        dfs(node, node);
    }

    for(auto node : table[T]) {
        memset(visited, false, sizeof(visited));
        visited[node] = true;
        dfs(node, node);
    }
}

int getAnswer()
{
    int ret = 0;
    vector<int> checkArr(MAX_N, 0);
    
    // S에서 방문가능한 모든 정점
    for(int i=0; i<table[S].size(); i++){
        checkArr[table[S][i]]++;
    }

    // T에서 방문가능한 모든 정점
     for(int i=0; i<table[T].size(); i++){
        checkArr[table[T][i]]++;
     }

    // S, T로 갈 수 있는 모든 정점
    for(int node=1; node<=n; node++){
        if(find(table[node].begin(), table[node].end(), S) != table[node].end()) {
            checkArr[node]++;
        }
        if(find(table[node].begin(), table[node].end(), T) != table[node].end()) {
            checkArr[node]++;
        }
    }

    for(int node=1; node<=n; node++){
        if(checkArr[node] == 4) ret++;
    }
    
    return ret;
}

int main(int argc, char** argv)
{
    int m;
    cin >> n >> m;

    int from, to;
    for(int i=0; i<m; i++){
        scanf("%d %d", &from, &to);
        graph[from].push_back(to);
    }
    scanf("%d %d", &S, &T);

    updateTable();
    printf("%d\n", getAnswer());
    
    return 0;
}

시간초과 원인

• DFS 호출이 너무 많다. 노드가 최대 10만개인데 DFS 를 최악의 경우 DFS 를 10만개의 노드에 대해서 해야한다.
• DFS 수행 횟수를 줄이기 위해 find() 함수를 활용하였으나 개선되지 않았다.

문제접근2

• 문제접근1 에서 3번, 4번 조건을 확인하기 위해서 모든 노드를 시작점으로 DFS 를 했던 점을 개선하기 위해 역방향 그래프 에 대해 공부했다.
• 역방향 그래프를 만들고 출발점 S, T 에서 DFS 를 하면 방문하는 노드들이 각각 S 에 도달할 수 있는 모든 노드들, T 에 도달할 수 있는 모든 노드들이 된다는 것을 이해했다.
• 즉, DFS 4번이면 문제 해결을 위한 4가지 조건을 모두 찾을 수 있다.
• 4번의 DFS 에서 모두 방문된 노드들의 개수가 정답이 된다.

구현2

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>

#define MAX_N 100001

using namespace std;

int n, S, T;
bool step1[MAX_N];
bool step2[MAX_N];
bool step3[MAX_N];
bool step4[MAX_N];
vector<int> forwardGraph[MAX_N];
vector<int> reverseGraph[MAX_N];

void dfs(int node, vector<int> graph[], bool visited[])
{
    for(int i=0; i<graph[node].size(); i++) {
        int nextNode = graph[node][i];
        if(visited[nextNode]) continue;
        visited[nextNode] = true;
        dfs(nextNode, graph, visited);
    }
}

int getAnswer()
{
    int ret = 0;
    for(int node=1; node<=n; node++){
        if(node == S || node == T) continue;
        if(step1[node] && step2[node] && step3[node] && step4[node]) ret++;
    }
    return ret;
}

int main(int argc, char** argv)
{
    int m;
    cin >> n >> m;

    int from, to;
    for(int i=0; i<m; i++){
        scanf("%d %d", &from, &to);
        forwardGraph[from].push_back(to);
        reverseGraph[to].push_back(from);
    }
    scanf("%d %d", &S, &T);

    memset(step1, false, sizeof(step1));
    memset(step2, false, sizeof(step2));
    memset(step3, false, sizeof(step3));
    memset(step4, false, sizeof(step4));
    step1[S] = true; step1[T] = true; // T를 거쳐서 도달하는 노드는 안됨
    dfs(S, forwardGraph, step1);
    step2[T] = true; step2[S] = true; // S를 거쳐서 도달하는 노드는 안됨
    dfs(T, forwardGraph, step2);
    step3[S] = true;
    dfs(S, reverseGraph, step3); //  S로 도달할 수 있는 모든 노드
    step4[T] = true;
    dfs(T, reverseGraph, step4); // T로 도달할 수 있는 모든 노드
    cout << getAnswer() << endl;
    return 0;
}