https://www.acmicpc.net/problem/4013
티어: 플래티넘 2
로직
어떤 교차로와, 그 교차로가 속한 SCC 안의 교차로는 자유롭게 움직일 수 있으므로, SCC 단위로 돈을 구해줘야 합니다.
SCC를 추출한 뒤, SCC 단위로 위상 정렬을 하며 SCC에 도달할 때까지 출금할 수 있는 최대 금액 + 그 SCC에서 출금할 수 있는 금액을 저장합니다.. 시작 지점이 정해져 있으므로 시작 지점에서 도달할 수 없는 곳은 따로 표시해줍니다.
시작 지점에서 출발해 도달할 수 있는 곳중 출금할 수 있는 금액이 문제의 답이 됩니다.
'백준 & 알고리즘' 카테고리의 다른 글
| [파이썬] 백준 26157번 - 즉흥 여행 (Hard) (0) | 2023.10.16 |
|---|---|
| [파이썬] 백준 3682번 - 동치 증명 (0) | 2023.10.15 |
| Top-down DP와 Bottom-up DP의 차이점과 장단점, 쓰는 경우 (1) | 2023.06.23 |
| [파이썬] 백준 1111번 - IQ Test 풀이 (0) | 2023.06.23 |
| [파이썬] 백준 1354번 - 무한 수열 2 풀이 (0) | 2023.06.23 |
