4013. ATM

계절학기를 대면수업할 줄은 몰랐는데.. 덕분에 매일 출근길 지하철을 타고 있다. 너무 덥다.

4013번: ATM

---

일방통행인 길을 따라 교차로를 지나가며 현금을 최대한 많이 인출하면서 레스토랑에 가야 한다. 만약 길이 일방통행이 아니었다면 실버 5 문제가 되었을 텐데.. 아쉽게도 유향 그래프이기 때문에 다른 방법을 생각해야 한다.

 

문제의 그림에서도 볼 수 있듯이 그래프에는 사이클이 존재할 수 있다. 사이클은 갈 수 있다면 가는 것이 무조건 이득이다. 돈을 얻거나 적어도 잃지 않으면서 원래 위치로 무조건 돌아올 수 있기 때문이다. 따라서 사이클은 하나의 큰 노드로 묶어서 생각하는 것이 좋다.

 

사이클을 묶으려면 SCC(강한 결합 요소)를 사용해야 한다. SCC는 서로 도달할 수 있는 정점의 집합인데, 여기서는 SCC에 대한 설명은 생략하겠다. 그래프에서 SCC를 찾고, SCC끼리의 그래프를 새로 만들자. 이때 현금, 레스토랑 존재 여부, 간선 등을 모두 생각해야 한다.

 

SCC의 그래프를 만들었다면 이제 그래프를 탐색해야 한다. 나는 다익스트라에서 최단 거리를 구할 때처럼 우선순위 큐를 이용하여 그래프를 탐색하였다. 다익스트라가 거리 값을 작게 하듯이, 나는 인출할 수 있는 돈을 크게 하는 방향으로 정답을 구했다. 

 

그런데 다른 분들의 풀이를 보니 위상 정렬로도 가능한 듯 하다. 위상 정렬($O(V+E)$)은 약 400ms 정도 걸리는데, 내 풀이($O(VE)$)는 1156ms 걸렸다. 나름 신나게 풀었는데 풀이가 비효율적인 걸 알게 되니 묘하네..

---

시루세리의 모든 도로가 실제로 일방통행인지는 잘 모르겠다. 검색해 봐도 관련 정보가 없다.