[ SWEA 5684 ] 운동 (C++)

SWExpertAcaemy의 운동(5684 / D4) 문제이다.

[ 문제풀이 ]

도로의 정보들을 통해서 도로의 길이의 합이 가장 작은 사이클을 찾아야 하는 문제이다.

본인은 완전탐색을 통해서 접근해 보았다.

깊이우선탐색을 이용해서 모든 정점에서 시작을 해서, 다시 시작한 정점으로 돌아왔을 때, 그 비용이 최소가 되는지

체크해 주었다.

하지만 ! 반드시 모든 정점에서 계산을 해볼 필요는 없다. "현재 정점으로 들어오는 길이 없는 정점"에 대해서는

체크를 해주지 않아도 된다.

왜냐하면 현재 정점으로 들어오는 길이 없다 라는 말은 해당 정점에서 출발해서 다시 해당 정점으로 돌아오는 경우가

없다라는 것을 의미하고 결국 사이클이 존재할 수 없는 정점이기 때문이다.

DFS함수 안에서는, 현재 정점과 연결되어 있는 모든 정점들을 방문체크를 함과 동시에 하나씩 탐색해 주었는데

"이미 방문한 정점"에 대한 또 다른 처리도 해 주었다.

왜냐하면 시작 정점은 이미 가장 처음에 "방문했습니다" 라고 표시를 해둔 상태일 것이고, 이 상태에서 이미 방문한 정점을

그냥 지나쳐 버린다면 절대 사이클을 확인할 수 없기 때문이다.

따라서, 현재 정점과 연결되어 있는 또 다른 정점을 갈 때, 그 정점이 이미 방문 처리 된 정점이라면, 그 정점이 시작정점인지

확인해 주는 과정이 필요하다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 410
using namespace std;
 
int N, M, Answer;
int Entry[MAX];
bool Visit[MAX];
vector<pair<int, int>> V[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        Entry[i] = 0;
        V[i].clear();
        Visit[i] = false;
    }
    Answer = 2e9;
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        V[a].push_back(make_pair(b, c));
        Entry[b]++;
    }
}
 
void DFS(int Cur, int Sum, int Start)
{
    Visit[Cur] = true;
    for (int i = 0; i < V[Cur].size(); i++)
    {
        int Next = V[Cur][i].first;
        int Cost = V[Cur][i].second;
 
        if (Visit[Next] == false)
        {
            if (Sum + Cost < Answer) DFS(Next, Sum + Cost, Start);
        }
        else
        {
            if (Next == Start) Answer = Min(Answer, Sum + Cost);
        }
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (Entry[i] == 0) continue;
 
        memset(Visit, false, sizeof(Visit));
        DFS(i, 0, i);
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}