그래프 알고리즘
spfa, floyd-warshall
[풀이]
예전에 풀었던 문제이나, 동아리 리뷰 문제로 나온 문제중 레이팅이 가장 높고, 이전에 짰던 코드를 보니 굉장히 복잡해서 더 간단하게 풀어보기 위해 건드려보았다.
먼저, '최대'이윤을 구하는 문제이고 문제 정의상 음수 간선에서 양수 cycle을 판별해야하는 문제이기 때문에 spfa로 해결이 가능하다.
일반적으로 spfa에서 cycle을 판별하듯이 판별하여 cycle이 있으면 바로 'Gee'를 출력하면 해결이 될까?
0 2 0
0 1 9999
1 2 9999
2 1 9999
0 3 0
10000 10000 10000 10000
이런 입력이 들어온다고 치자. 1과 2에서 cycle이 발생하므로 일반적으로 cycle판별 후 있을 때 return하면 'Gee'를 출력할 것이다. 하지만, 그림을 보면 알 수 있듯이 3은 무한한 이익을 얻지 못 하고, 20000밖에 얻지 못 한다.
따라서, graph내에 cycle이 있더라도 그 cycle이 destination에게 영향을 주지 못 한다면 무시해야 할 cycle이다. 즉, cycle이 발생하면 그 cycle에서 destination까지의 경로가 있는지 판별하고, 경로가 있으면 cycle의 영향을 받기 때문에 무한한 이익이 발생하기 때문에 'Gee'를 출력해주면 된다.
destination까지의 경로 유무 판별하는 방법은 여러가지가 있으나, 가장 빠른방법은 매 cycle로 판별되는 vertex마다 bfs를 돌며 check하는 것이고, 가장 간단한 방법은 미리 플로이드와샬을 돌려서 두 정점이 연결되어 있는지 미리 판별해놓는 방법이 있다.
풀이는 간단하지만 생각보다 시행착오를 많이 겪었는데, 대표적으로 cycle[destination]이 $n$일 때 cycle로 판별 해 주면 안 되나? 라는 생각으로 접근했었다. 아래 case가 반례이다.
0에서 시작해서 2로 바로 가기 때문에 dist[2]가 20000이 되고, 1에서는 계속 loop을 돌며 dist[1]만 1씩 늘어날 것이다. $n$이 3이기 때문에, cycle[1]만 3이 되고, cycle[2]는 1인 상태로 멈출 것이기 때문에 cycle판별이 불가능하다.
즉, cycle과 연결된 다른 vertex들이 매번 update되지 않기 때문에 불가능하다.
따라서, 기존의 방식으로는 cycle로 인한 무한 이익이 발생하는지 판별이 불가능 하기 때문에, cycle의 child node로 destination이 있는지 판단 해주어야하고, 그러기 위해 플로이드와샬을 써서 총 O($n^3$)으로 판별이 가능하다.
