mad robot1 #1405 미친 로봇(Full Search, Back Tracking) 이번 문제는 경로를 다니면서, 지나온 길을 거치지 않을 확률을 계산하는 것입니다. 난이도 Gold V로 어렵지는 않은 문제이고요. 복잡한 알고리즘이 아니라, 단순한 백트랙킹을 구현하면 됩니다. 동서남북으로 움직일 수 있는 확률이 주어지고, 동서남북으로 확률적으로 N칸 움직였을 때, 지나온 경로를 다시 방문하지 않는 경로로 움직일 확률이 얼마일까를 계산하는 문제입니다. 예를 들어서 로봇이 NESW로 순차적으로 움직였다면, 원위치로 돌아왔으니, 지나온 경로를 지나게 됩니다. NNES 라던지, SWWS 와 같은 경로는 4칸을 움직이면서 지나온 경로를 지나지 않는 움직임이 됩니다. 문제를 풀기 위해서는 BFS, DFS 들 중 어떤 것을 사용하든 상관이 없습니다. 전 편한 DFS를 사용했습니다. 최대 움직임은 1.. 2020. 2. 23. 이전 1 다음 728x90
