시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 161 | 44 | 29 | 36.250% |
유명한 영웅 백준은 퀘스트를 받아 혼자 모험을 하는 중에 미로를 발견하였다. 미로 주변으로 길이 없으므로 백준은 반드시 미로를 통과해야 한다.
백준은 이 미로를 잘 모르기 때문에 길이 나누어지면 그 중 무작위로 길을 택해 그쪽으로 이동할 것이다. 또한 백준은 완벽한 기억력을 가졌기 때문에 같은 길을 두 번 들어서는 일은 없고 더 이상 길이 없을 거라고 확신했을 때만 왔던 길을 돌아갈 것이다. 즉, 왔던 길을 돌아가기 전까지 안 가본 길은 다 둘러볼 것이다.
백준의 동료인 당신은 백준이 떠나고 뒤늦게 미로의 정보를 가지고 있는 지도를 발견하고는 백준이 미로를 탈출하는데 얼마나 걸릴지 궁금해서 걸음의 기댓값을 구하고자 한다. 당신은 미로를 잘 살펴본 결과 미로는 같은 지점으로 돌아오는 사이클이 없고 2×2 이상의 공간이 없다는 것을 알았다. 미로에는 입구와 출구가 각각 하나만 있고 길 옆에 출구가 있더라도 길이 나누어져 있다고 가정한다.
아래의 간단한 지도의 예를 보자.
##s### #....# #t####
입구는 "s"로 표시되어 있고 출구는 "t"로 표시되어 있다.
입구에서 남쪽으로 1칸 이동했을 때 길이 갈라지는데 여기서 서쪽을 선택하고 2칸 이동하면 출구를 찾을 수 있다. 반면 동쪽을 선택했을 시 4칸 이동하여 다시 돌아오고 남은길이 서쪽밖에 없으므로 서쪽으로 2칸 이동하면 출구를 찾을 수 있다.
따라서 백준이 입구에서 출구까지 나가는데 걸음의 기댓값은 \( 1 + \frac{1}{2} \cdot (4 + 2) + \frac{1}{2} \cdot 2 = 5 \) 이다.
i번째 테스트 케이스에 대해 i번째 줄에 걸음의 기댓값을 반올림하여 둘째 자리까지 출력한다.
1 3 6 ##s### #....# #t####
5.00
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2008 Preliminaries C번