벨만-포드. [1865]

[1. 문제 설명]

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

---

[2. 풀이 접근]

문제 풀이 시 약간 애매할 수 있는 부분.

1. 출발지가 어디인가?
2. 되돌아오는 경로가 있는지 어떻게 확인하는가?

내가 최종적으로 제출한(혹은 타당하다고 생각하는) 코드는 플로이드-워셜을 이용한 풀이이다.

• 이 문제에서 음수 사이클은 중요하지 않다고 생각함.
• 사이클을 지나되, 무한 루프에 빠진 경로가 아니고, 이 음수 사이클을 적당히 지난 경로라고 생각하면 됨.
• 그림.. 추가하도록,
• 즉, 최종적으로 출발지로 되돌아 오는 것이 더 중요하다고 생각하며,
• 되돌아 왔을 때, 시간이 되돌아가 있는지(시간이 음수가 되는지) 를 판단하는 것이 옳다고 생각하기 때문이다.
• 또한 플로이드-워셜은 모든 출발지-도착지 간의 최단 거리를 구할 수 있다.
• 즉, 모든 출발지에 대해서 검증할 수 있다는 것이다.

이와 별개로, 아래와 같은 풀이를 생각 해볼 수 있다. 

• 모든 시작점에 대해서 벨만-포드 사용을 생각해 볼 수 있음.
• 출발지(src) 로 되돌아 왔을 때, 시간이 과거로 이동한 경로는 dist[src] < 0 이 된 경우
  => 최초 dist[src] = 0 이었으므로
• 그러나 이 풀이는 시간 초과를 유발한다.

그러나 벨만-포드 풀이에서 시작점 위치를 아무 곳이나 잡아도 음수 사이클이 있다면 "YES" 를 출력 할 수 있다.

이 시작점에서 되돌아오는 경로인지 마땅히 확인이 된것도 아닌데, 왜, 그럴까?

이와 관련한 좋은 글

• https://www.acmicpc.net/board/view/72995

정리하면 아래와 같다,

1. 이러한 풀이는 옳바른 벨만-포드 구현이 아니지만, 이 문제에서는 올바른 풀이가 된다.
   => INF 간 덧셈 연산이 오버플로가 안나게 구현하면 상관 없음(?).
   => 2*INF 가 maxInt 보다 작게 되도록, 
2. ∀ v, dist[v] = INF,  dist[v] == INF 는 v 를 아직 방문했다는 것이 아니라, v 를 INF 걸려 방문했다는 의미가 된다.
   => v 를 아직 방문하지 못했다는 의미에서 풀이를 하려면, 
   => 모든 시작점에 대한 벨만-포드 를 이용한 풀이가 정확하며,
   => 시간 초과를 해결하려면 다음과 같이 해야 한다.
        1. 모든 정점에서 동시에 시작, (∀ v, dist[v] = 0)
        2. 이 상태에서 벨만-포드 수행.
3. 즉, 모든 시작점에 대해서 일단 방문했다는 의미가 되며,
4. 음수 사이클이 있기만 하면, 이 사이클을 적당히 거치고(weight 가 점점 감소), 되돌아 가는 경로가 있다는 것이 된다.
   => 플로이드-워셜 풀이에서 설명한 것과 같은 맥락.

 

끝으로 그래프 생성 시 주의해야 할 부분

1. 일반 도로는 양방향 도로,
2. 웜홀은 단방향 도로,
3. 일반 도로는 최대한 |T| 가 작은 값을 써야하고,
4. 웜홀은 최대한 |T| 가 큰 값을 써야한다.

3, 4, 는 음수 사이클을 유발하기 위함이다.

---

[3. 코드 - 벨만-포드]

a

---

[4. 코드 - 플로이드-워셜]

a