2468ab   6년 전

기본문제인거같은데 10번을넘게 틀리네요.. ㅠㅠ 

코드는 간단하게 map을 40,40 정도로 잡아두고 (20,20)에서 시작했습니다.

기본적으로 bfs를 사용하여

첫번째 방은 map = 1, 그후 탐색을 진행하면서 하나씩 더해나갔습니다.

이때  map의 다음방이 이전방의 값보다 1 크다면 ans 값에 전방의 확률 * 진행방향의 확률 을 더해주었습니다

탐색은 map값이 n+1 이 나오는 순간 멈추었고

마지막에 map == n+1인 방들의 확률을 더해 출력했습니다 왜 틀릴까요... ㅋㅋㅋㅋ 슬프네요

djm03178   6년 전

BFS로 간단히 풀릴 문제는 아닌 것 같습니다. 여러 경로에서 모두 거치게 되는 칸이 많이 있을 수 있고, 어떤 경로가 단순한지 여부는 딱 그 경로에서 지나쳐 온 칸들이 무엇인지 알아야 판단할 수 있는데 이 경우 다른 쪽에서 온 칸도 모두 계산에 포함하기 때문에 제대로 판별할 수 없습니다.

반례를 드리자면, 다음과 같은 예시에서 0.5625가 나와야 합니다.

3 25 25 25 25

2468ab   6년 전

@djm03178

아 죄송합니다 질문해두고 다른 문제 풀다보니 까먹고 있었네요.

처음에 생각을 잘못 했었네요 n번째의 가장 단순한 경로를 bfs의 마지막 칸이라고 생각했었는데 생각이 짧았습니다.

대답 감사합니다 ㅠㅠ 고생하세요.

댓글을 작성하려면 로그인해야 합니다.