벨만포드1 백준 1865 c++ -[PlusUltraCode] [필자 사고] 문제를 해석해 보니 다음과 같은 결론을 내렸다. 1. 출발해서 다시 원점으로 돌아와야 된다. => 사이클이 있다. 2. 웜홀을 통해 내가 쓴 시간보다 더 적은 시간을 사용해야 된다 => 음수 사이클이 있다. 이를 통해 음수 사이클을 대표적으로 판단할 수 있는 벨만포드 알고리즘이 떠올랐다. 벨만포드 알고리즘을 간단하게 설명하겠다. 모든 간선들의 조사를 N-2번 조사한다. 그 후 마지막 한번도 모든 간선들을 조사 했을 때 Distance의 값중 하나가 바뀌게 된다면 음수 사이클이 존재한다는 것을 판별 할 수 있게 된다. [소스 코드] #include #include using namespace std; typedef struct Node { int start; int end; int weigh.. 2024. 2. 22. 이전 1 다음