topological_sorting 썸네일형 리스트형 BOJ 4013 - ATM (P2) https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 사용 알고리즘 SCC + 위상정렬 DP 풀이 ATM에서 현금을 인출할 때, 어떤 정점에서 사이클이 존재한다면 그 사이클을 쭉 돌면서 사이클에 속하는 모든 정점의 ATM을 이용할 수 있다. 따라서 사이클 내의 정점들을 묶어 생각할 수 있고, 하나의 SCC로 묶어줄 수 있음을 알 수 있다. 예제 그래프이다. 위에 적힌 숫자는 ATM에서 인출할 수 있는 현금이고, 색칠된 숫자는 그 정점에.. 더보기 이전 1 다음
