Approach
일단, 그리디한 관점으로 보면 가능한 ATM 기기를 최대한 많이 거쳐가는 것이 유리하다.
하지만, 모든 ATM 기기를 전부 다 갈 수 없는데, 그 이유는 Directed graph이기 때문이다.
그런데, SCC에서는 위 문제가 완전히 해결된다.
SCC의 특성이 해당 컴포넌트 내부에서 임의의 두 노드를 잡았을 때 반드시 해당 두 노드를 연결하는 path가 존재한다는 것이다.
즉, SCC 내부에 존재하는 ATM은 전부 다 방문할 수 있게 된다.
또한 추가적으로 SCC를 만들게 되면 장점이 DAG가 만들어진다는 것이다.
이를 이용하여 Topological sorting을 할 수 있게 된다.
즉, SCC단위로 ATM기에 존재하는 금액의 총 합, 레스토랑 존재 여부를 다룰 수 있고
위 문제는 출발 지점이 속하는 SCC에서 레스토랑이 존재하는 SCC 들 중 금액의 최댓값을 구하는 문제로 변경되고
DAG이므로 DP를 통해 쉽게 구할 수 있다. (Shortest path에서 DAG가 보장되면 DP로 풀 수 있는 뉘앙스와 거의 유사하다.)
Code