BOJ 1219 오민식의 고민

어렵다.
Bellman-Ford algorithm을 사용하면 되긴하는데, 출력 조건에 맞춰 출력하는 부분에서 Bellman-Ford algorithm과 이 문제에 대한 깊은 이해가 필요하고 많은 고민이 필요해 보인다.

판별해야 하는 상황은 다음과 같다.
1. 도착도시에 도착하는 것이 불가능할 때
2. 무한대의 돈을 벌 수 있을 때
3. 도착도시에 도착하는 것이 가능하면서 무한대의 돈을 버는 것은 아닐 때

다음과 같이 판별해볼 수 있겠다.
1. 출발도시에서 도착도시까지 도달하는 것이 불가능하다면 upper값으로 설정한 NEGINF에 100만씩 100번 완화할 수 있으므로 upper[des]값이 NEGINF인 경우만 도달 불가능하다고 보면 안되고, NEGINF+100*1,000,000 이하인 경우를 도달 불가능하다고 봐야할 것이다.
- JM book 참고하기

2. 단순히 양수 사이클이 있는 경우라고 생각하기 쉽다. 하지만 아니다.
양수 사이클이 존재하면서 그 양수 사이클에서 도착도시까지 갈 수 있어야 한다.
양수 사이클이 존재하지만 양수 사이클에서 도착도시로 갈 수 없다면 돈을 벌 수 없기 때문에 그 경우는 양수 사이클로 가지말고 도착도시로 가야한다.

3. 사이클이 없거나, 사이클이 있더라도 그 사이클에 빠지면 도착도시로 갈 수 없는 경우이다.

** 2, 3을 구별해서 하는 것이 문제이다. 사실 이것들을 생각하지도 못했는데, 질문 게시판에 있는 고수들의 질문과 답변을 보고 알았다.


실제 테스트할 때는,
4 0 3 4
0 1 0
1 2 0
2 1 0
0 3 10
10 10 10 10 으로 테스트 해보면 된다.









만약 사이클이 있고 그 사이클에서 도착도시까지 연결돼 있다면 n번째 갱신할 때, 도착도시까지 가는 경로가 갱신될 줄 알았는데... 이 예제를 보면 그렇지 않다는 것을 알 수 있다!

사이클이 있는지는 판단하기 쉽지만, 그 사이클에서 도착도시까지 갈 수 있는지 없는지를 판단하기가 어렵다. 어떻게 해야할까?

일단 사이클이 있다면 n번째 갱신할 때, 사이클에 포함된 도시가 갱신될 것이다. 그럼 그 도시부터 시작해서 도착도시까지 갈 수 있는지 dfs로 알아보면 될 것 같다. -> 생각해보니 n번째 갱신할 때 사이클에 포함되지 않은 도시도 갱신될 수 있을 것 같다... 그럼 어떻게 사이클에 포함된 도시를 알 수 있을까? -> 잘 모르겠지만, 이 문제에서는 사이클에 포함된 도시를 골라낼 필요가 없다. n번째 갱신할 때, 갱신되는 도시중에는 사이클에 포함되지 않은 도시도 있겠지만, 그 도시는 사이클로부터 온 도시일 것이다. 결국, n번째 갱신할 때 갱신되는 도시가 어떤 도시든 그 도시에서 도착도시까지 갈 수 있다면, 사이클에서 도착도시까지 갈 수 있는 것이다....

그리고, 사이클이 있으면 시작도시에서 사이클이 있는점까지 갈 수 있는지도 체크해야 한다.좀 간편하게 하기위해 플로이드와샬로 각 도시간에 이동할 수 있는지를 체크해놓는 것도 괜찮고, 아니면 벨만포드를 구현할 때, here, there가 있어서 here를 이용해서 there를 갱신하는데, here가 NEGINF(INF)인 경우(즉, 시작점에서 here까지 도달 못한 경우) 갱신이 안되게 하면, 사이클이 있어도 시작점에서 갈 수 없는 사이클이라면 사이클을 찾아낼 수 없을 것이다.
그리고 이렇게 구현하면 좋은 것이, 도착도시에 도달할 수 없는지 판단할 때 그냥 NEGINF(INF)인지 아닌지만 보면된다.
이런 구현 방식은 kks227님 블로그를 참조했다.

 그래서 난 일단 here가 NEGINF(INF)인 경우 갱신이 안되게 하고, n번째 갱신할 때 갱신되는 도가 있다면(사이클이 있다면) 갱신되는 점들 중 하나라도 도착도시와 연결이 된다면 돈을 무한히 벌 수 있는 것으로 판정할 것이다.

일단 AC를 받았다.
벨만포드에 대해 잘 알고있다고 생각했는데... 전혀 그렇지 않았고... 오히려 배웠다.
정말 공부가 되는 좋은 문제이다... 나중에 꼭 다시 풀어보기. 생각해보기.