Softeer [level 3] : 출퇴근길 (C++ 언어)

https://softeer.ai/practice/info.do?idx=1&eid=1529&sw_prbl_sbms_sn=172424 

Softeer

Code:

 

#include <iostream>
#include <vector>
 
using namespace std;
vector<int> graph[100005];
vector<int> graphR[100005];
int starts[100005] = { 0, };
int startt[100005] = { 0, };
int startsR[100005] = { 0, };
int starttR[100005] = { 0, };
 
void dfss(int num)
{
    if (starts[num] == 1)
    {
        return;
    }
    starts[num] = 1;
    for (int i = 0; i < graph[num].size(); i++)
    {
        int y = graph[num][i];
        if(!starts[y])
        dfss(y);
    }
}
void dfst(int num)
{
    if (startt[num] == 1)
    {
        return;
    }
    startt[num] = 1;
    for (int i = 0; i < graph[num].size(); i++)
    {
        int y = graph[num][i];
        if (!startt[y])
        dfst(y);
    }
}
 
void dfstR(int num)
{
    if (starttR[num] == 1)
    {
        return;
    }
    starttR[num] = 1;
    for (int i = 0; i < graphR[num].size(); i++)
    {
        int y = graphR[num][i];
        if (!starttR[y])
            dfstR(y);
    }
}
 
void dfssR(int num)
{
    if (startsR[num] == 1)
    {
        return;
    }
    startsR[num] = 1;
    for (int i = 0; i < graphR[num].size(); i++)
    {
        int y = graphR[num][i];
        if (!startsR[y])
            dfssR(y);
    }
}
 
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    int x, y, s, t;
    while (m--)
    {
        cin >> x >> y;
        graph[x].push_back(y);
        graphR[y].push_back(x);
    }
    cin >> s >> t;
    starts[t] = 1;
    startt[s] = 1;
    dfss(s);
    dfst(t);
    dfssR(s);
    dfstR(t);
    int count = 0;
    for (int i = 1; i <= n; i++)
    {
        if (starts[i] == 1 && startt[i] == 1&&i!=s&&i!=t&&startsR[i]==1&&starttR[i]==1)
        {
            count++;
        }
    }
    cout << count;
}

문제풀이:

c언어로 어떻게 100000개의 경로를 표현할지 생각이 안나서.. c++로 해결하였다.

문제풀이는 전체적으로 나열하여 적었다. 함수도 dfs하나로 해결할 수 있지만 4가지를 만들었다.

순방향으로 check를 해준다음에 역방향으로 check를 해줬다. 출발지점과 도착지점도 고려하였다.

c로 푼게 아니므로 설명은 대강 하겠다.