[ BOJ 백준 1865번 - 웜홀 ] 해설 및 코드

https://www.acmicpc.net/problem/1865

 

목적

음의 가중치가 존재하는 방향 그래프에서 음의 사이클이 존재하는지 알아내자.

 

접근법

1. 최단 거리를 구하기 위해 흔히 알려진 3가지 알고리즘 중에 음의 가중치가 존재할 때 최단 거리를 O(VE)의 시간복잡도로 구할 수 있는 '벨만 포드'로 접근하자.

 

2. 출발지로부터 모든 정점으로의 최단거리를 갱신하면서, 출발지인 정점 1의 최단 거리가 음수가 되는 순간, 음의 사이클이 존재한다는 결론으로 귀결난다.

 

3. V번째 loop를 돌고 값의 갱신 여부를 확인한다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;

int n,m,w,size,edge[5201][3],d[501];

bool sol(){
	f(i,1,n)d[i]=5e6;
	d[1]=0;
	int cnt=size;
	bool updated;
	while(cnt--){
		updated=false;
		f(j,1,size){
			int tmp=d[edge[j][0]]+edge[j][2];
			if(d[edge[j][1]]>tmp){
				if(edge[j][1]==1)return true;
				d[edge[j][1]]=tmp,updated=true;
			}
		}
		if(!updated)return false;
	}
	return updated;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc;cin>>tc;
	while(tc--){
		cin>>n>>m>>w;
		size=0;
		while(m--){
			int s,e,t;cin>>s>>e>>t;
			size+=2;
			edge[size-1][0]=edge[size][1]=s;
			edge[size-1][1]=edge[size][0]=e;
			edge[size-1][2]=edge[size][2]=t;
		}
		while(w--){
			int s,e,t;cin>>s>>e>>t;
			++size;
			edge[size][0]=s;
			edge[size][1]=e;
			edge[size][2]=-t;
		}
		
		cout<<(sol()?"YES":"NO")<<'\n';
	}
	return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.