[BOJ 10319] 좀비 아포칼립스

문제 출처 : https://www.acmicpc.net/problem/10319

10319번: 좀비 아포칼립스

 

풀이 :

 

네트워크 플로우 최대 유량 문제입니다.

 

소스와 싱크를 만들어 소스 -> 시작장소, 병원 -> 싱크로 연결해 줍시다.

 

각 엣지 별로 단위 시간에 통과할 수 있는 사람 수, 걸리는 시간에 대한 정보를 추가적으로 활용해야합니다.

 

저는 Flow에 대한 정보를 단위시간별로 쪼개서

단위 시간에 통과할 수 있는 사람 수와 현재 시각에 통과한 사람 수를 계산하여 경로를 탐색하였습니다.

 

그러기 위해서 각 엣지별로 Flow에 대한 정보를 단위시간만큼의 배열을 만들어 계산하였고,

단위시간을 관리 하기 위해서 Source에서 0~s 만큼 출발시간을 설정해주어 Network Flow를 진행하였습니다.

 

이렇게 풀이를 하게 될 시 최대 유량이 일행 수를 초과할 수 있으니 조건문으로 잘 걸러주시면 됩니다.

 

정석 풀이는 정점 분할을 이용한 풀이 인것 같으니 정점 분할 풀이에 대한것도 한번 찾아보면 좋을 것 같습니다.