[C++, 코딩테스트] Softeer : 출퇴근길 with DFS

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

 

출퇴근길 문제는 DFS로 풀어야하는 걸 알겠지만 DFS의 탈출 조건에 대해서 이해하고 생각하는데 어려움을 느꼈다. 

 

// DFS 레츠고
#include<iostream>
#include<vector>

using namespace std;

int visitedStoT[100001];
int visitedTtoS[100001];
vector<int> dir[100001];
int N, M;
int S, T;

bool go(int cur, int end, int visited[]){
    vector<int> &tmp = dir[cur];
    bool pass = false;
    for (int i = 0; i < tmp.size(); i++){
        if (tmp[i] == end){ // 목적지에 도착하면 true로 바꾼다.
            pass = true;
            visited[tmp[i]] = 1;
            continue;
        }
        if (visited[tmp[i]] == 1){ // 이미 증명이 된 노드 체크
            pass = true;
            continue;
        }
        visited[tmp[i]] = 1;
        if (!go(tmp[i], end, visited)){ // 모든 길을 탐색해서 목적지에 도착할 수 있는 노드인지 확인
            visited[tmp[i]] = 0; // false가 나온 경우 탐색 0으로 만든다.
        } else {
            pass = true;
        }
        
    }
    return pass;
}

int count(){
    int count = 0;
    for (int i = 1; i <= N; i++){
        if (i == S || i == T)
            continue;
        if (visitedStoT[i] == 1 && visitedTtoS[i] == 1){
            count++;
        }
    }
    return count;
}

int main(int argc, char** argv)
{
    cin >> N >> M;
    for (int i = 0; i < M; i++){
        cin >> S >> T;
        dir[S].push_back(T);
    }
    cin >> S >> T;
    visitedStoT[S] = 1;
    visitedTtoS[T] = 1;
    go(S, T, visitedStoT);
    go(T, S, visitedTtoS);
    cout << count() << endl;
    return 0;
}

 

go 함수는 dfs 알고리즘으로 선택한 노드로 갈 경우에 목적지를 도착할 수 있는지를 알려준다.

 

내가 헷갈렸던 부분은  dfs의 탈출 조건인데 이게 생각하기 힘들었던 이유는 

 

S에서 T로 가는데 4 -> 7로 가면 T로 갈 수 없기 때문에 4로 다시 돌아가야한다. 하지만 7도 T로 가는 길에 포함되기 때문이다. 그래서 재귀를 돌면서 어떻게 탈출 조건을 넣어줄지 머리가 꽤나 아팠다.

간단히 생각해서 재귀가 결과(bool)를 반환해서 알려주고 목적지를 방문했는지에 기록해놓는다면 길이 없는 노드에 갔더라도 방문 기록을 0으로 만들어서 카운트를 안할 수 있다.

 

다른 분의 코드를 이해하는데도 오래 걸렸고 단순히 방문 기록만하는 것이 아닌 결과값을 이용해서 유효한 루트인지도 확인할 수 있는 방법이 있다는 것을 배웠다.