SCC. [4013]

[1. 문제 설명]

위와 같이 교차로 에 ATM 및 레스토랑이 있을 때,

시작 점이 주어지고, 어떤 레스토랑까지 이동하면서

인출 할 수 있는 현금의 최대 액수를 구하도록 한다.

 

한번 출금하면 해당 ATM 에서는 더 이상 출금 할 수 없으며.

한번 지나간 edge 를 다시 지나갈 수 있다.

 

(원: ATM, 이중원: ATM + 레스토랑)

---

[2. 풀이 접근]

한번 지나간 edge 를 다시 지나갈 수 있으므로,

현금을 최대한 인출 하기 위해 cycle 을 형성 할 수 있다.

 

풀이 개요

1. 전체 그래프를 SCC 단위로 나눈다.
2. 시작 위치를 포함하는 SCC 에서 출발한다.
3. 레스토랑이 있는 SCC 를 방문 하는 모든 경우를 체크하여 최대 값을 구한다. 

최대한 많은 현금을 인출하기 위해

같은 SCC 에 속한 모든 노드를 전부 방문하고, 다음 SCC 로 이동하는 방식이다.

 

여기서 핵심은 바로 3 번 단계이다.

 

처음에 풀이한 방식은 dfs 를 통해서 최대 값을 갱신하는 것이었다.

그러나 이 풀이는 틀렸는데, 방문 순서에 따라서 최대 값을 갱신하지 못할 수 있기 때문이다.

 

아래 그림이 그 예시이다.

1 -> 2 -> 3 -> 4 방문 시 총 금액: 10

1 -> 999 방문 시 총 금액: 1000

 

 

그래서 dfs 에서 방문여부를 체크하지 않고 방문해보는 방식을 해보았다.

SCC 로 이루어진 그래프는 DAG 이므로, 부모/자식 노드간 cycle 은 발생하지 않기 때문이다.

=> cycle 이 발생한다면 이미 같은 SCC 로 묶여버렸을 것이다.

 

이 풀이는 시간 초과를 발생시켰다.

 

마지막 풀이는 

방문 여부 없이 bfs 를 수행하되,

해당 SCC 로 이동하여 인출된 현금의 누적 값이 더 커질 수 있는 경우에만 방문하는 것이다.

---

[3. 코드]