Coding Test/알고스팟
[C++] 알고스팟/동적계획법 - 두니발 박사의 탈옥
Junchoi
2020. 8. 26. 14:00
문제 링크
https://algospot.com/judge/problem/read/NUMB3RS
algospot.com :: NUMB3RS
두니발 박사의 탈옥 문제 정보 문제 위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았�
algospot.com
인접한 모든 마을을 dfs 방식과 같이 탐색하고 들어간 위치와 날짜를 메모이제이션을 해줍니다.
인접한 마을에서 날짜 d 만큼 지났을 때 감옥에 위치했는지에 대한 확률을 구하고 모든 인접한 마을에 대한 확률을 더해 최종 확률을 구해줍니다.
구현 코드