[백준 1865번] 웜홀 (재풀이 필요(시간초과) C++,벨만포드 풀이완료.)

해결완료

 

C++ 시간초과 코드

문제를 보고, 아 음의 싸이클이 있으면 YES로 출력하면 되나보다 하고 풀었다.

DFS를 사용해서 start지점과 똑같은 now에 도착하면 cycle이 있으며, sum값이 음수면 음의 싸이클이라 판단하고

return true

약 50%쯤에서 시간초과가 났다.

#include <bits/stdc++.h>

using namespace std;
//싸이클이 있는가.
//음의 싸이클인가.
vector<pair<int,int>> v[501]; //index = 출발지점, first = 도착지점, second = 가중치.
vector<int> Visit;
bool visited[501];
int N,M,W; // 각각 지점의 수, 도로의 개수, 웜홀의 개수.
bool dfs(int start,int now,int sum)
{
    if((int)Visit.size() > N) //방문한 노드개수가 총 노드수보다 커지면 return.
        return false;
    if(!Visit.empty())// 맨처음은 무시하고
    {
        //처음 방문한 노드와 현재방문한 노드가 같다면, cycle이 있음.
        //그때까지의 가중치 합이 음수면 음의 싸이클이 존재.
        if(start == now && sum <0)
        {
            return true;
        }
    }
    for(int i = 0 ; i<v[now].size(); i++)
    {
        int nn = v[now][i].first;
        int weight = v[now][i].second;
        if(visited[nn]==false) // 방문할 노드를 방문한적이 없으면
        {
            visited[nn] = true; //방문했다고 하고 
            Visit.push_back(nn);
            if(dfs(start, nn, sum+weight)) // 들어가서 다른노드 다시 탐색.
            {
                //dfs의 리턴값이 true로 돌아오면 지체없이 YES를 출력하기 위해 return True반복.
                return true;
            }
            Visit.pop_back();
            visited[nn] = false; 
        }
    }
    return false;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin>> T;
    //graph init.
    for(int i = 0 ; i< T; i++){
        for(int s = 1; s<=N; s++)
        {
            v[s].clear();
        }
        cin >> N>>M>>W;
        for(int a = 0; a<M; a++)
        {
            int s,e,w;
            cin >> s>>e>>w;
            v[s].push_back({e,w});
            v[e].push_back({s,w});
        }
        for(int b = 0; b<W; b++)
        {
            int s,e,w;
            cin >> s>>e>>w;
            v[s].push_back({e,-w});
        }
        bool dfsReturn=false;
        for(int it = 1; it<=N; it++)
        {
            Visit.clear();
            memset(visited,0,sizeof(visited));
            //시작노드 방문체크 안한상태로 dfs실시.
            //다시 되돌아 올때 visited False로 만들어주기 위해서.
            dfsReturn=dfs(it,it,0); //각 노드마다 dfs실시.
            if(dfsReturn)
            {
                //dfs의 return 값이 true라면 YES를 출력하고 break.
                cout << "YES" << endl;
                break;
            }
        }
        //dfs의 return값이 false라면 NO를 출력하고 다음 TestCase로.
        if(dfsReturn==false){
            cout << "NO" << endl;
        }
    }
}

 

C++ 벨만포드 풀이

#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;
vector<pair<int,int>> v[501];
int N,M,W; // 각각 지점의 수, 도로의 개수, 웜홀의 개수.
int dist[501];
bool bellman(){
    memset(dist, 0x7f,sizeof(dist));
    dist[1] = 0;
    bool changed = false;
    
    //N번을 반복할건데,
    for(int i = 0; i<N; i++)
    {
    	//모든 노드에 대해서 확인
        for(int j = 1 ; j<= N; j++)
        {
        	//해당 노드j가 가진 간선 확인.
            //j에서  n으로 , 가중치 w
            for(int k = 0; k<v[j].size(); k++)
            {
                int n = v[j][k].first;
                int w = v[j][k].second;
                //j노드에서 n번 노드로 가는길을 확인할건데
                //j노드까지 온 거리 + 가중치가 기존 n노드의 비용보다 적다면 갱신.
                if(dist[n] > dist[j]+w)
                {
                    dist[n] = dist[j]+w;
                    //벨만포드 알고리즘상 N-1번만 확인하면 최단경로가 구해지는데
                    //i==N-1(N번째)에도 최단경로가 갱신된다면 이는 음의싸이클을 가지는 그래프다.
                    if(i == N-1) changed = true;
                }
            }
        }
    }
    return changed; //return false(음의싸이클 안가짐) or return true(음의 싸이클 가짐)
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin>> T;
    //graph 입력받아서 초기화
    for(int i = 0 ; i< T; i++){
        cin >> N>>M>>W;
        //Graph setting
        //양방향 그래프
        for(int a = 0; a<M; a++)
        {
            int s,e,w;
            cin >> s>>e>>w;
            v[s].push_back({e,w});
            v[e].push_back({s,w});
        }
        
        //웜홀은 단방향 그래프이고, w값이 음수로.
        for(int b = 0; b<W; b++)
        {
            int s,e,w;
            cin >> s>>e>>w;
            v[s].push_back({e,-w});
        }
        
        //벨만포드 함수 실행해서 true면 YES, 아니면 NO
        if(bellman())
        {
            cout << "YES"<<endl;
        }else{
            cout << "NO"<<endl;
        }
        //다음 TestCase를 받기위해서 vector v 초기화.
        for(int a = 0; a<=N; a++)
        {
            v[a].clear();
        }
    }
}