1405번 - 미친 로봇
기본문제인거같은데 10번을넘게 틀리네요.. ㅠㅠ
코드는 간단하게 map을 40,40 정도로 잡아두고 (20,20)에서 시작했습니다.
기본적으로 bfs를 사용하여
첫번째 방은 map = 1, 그후 탐색을 진행하면서 하나씩 더해나갔습니다.
이때 map의 다음방이 이전방의 값보다 1 크다면 ans 값에 전방의 확률 * 진행방향의 확률 을 더해주었습니다
탐색은 map값이 n+1 이 나오는 순간 멈추었고
마지막에 map == n+1인 방들의 확률을 더해 출력했습니다 왜 틀릴까요... ㅋㅋㅋㅋ 슬프네요
BFS로 간단히 풀릴 문제는 아닌 것 같습니다. 여러 경로에서 모두 거치게 되는 칸이 많이 있을 수 있고, 어떤 경로가 단순한지 여부는 딱 그 경로에서 지나쳐 온 칸들이 무엇인지 알아야 판단할 수 있는데 이 경우 다른 쪽에서 온 칸도 모두 계산에 포함하기 때문에 제대로 판별할 수 없습니다.
반례를 드리자면, 다음과 같은 예시에서 0.5625가 나와야 합니다.
3 25 25 25 25
@djm03178
아 죄송합니다 질문해두고 다른 문제 풀다보니 까먹고 있었네요.
처음에 생각을 잘못 했었네요 n번째의 가장 단순한 경로를 bfs의 마지막 칸이라고 생각했었는데 생각이 짧았습니다.
대답 감사합니다 ㅠㅠ 고생하세요.
댓글을 작성하려면 로그인해야 합니다.
2468ab 6년 전
기본문제인거같은데 10번을넘게 틀리네요.. ㅠㅠ
코드는 간단하게 map을 40,40 정도로 잡아두고 (20,20)에서 시작했습니다.
기본적으로 bfs를 사용하여
첫번째 방은 map = 1, 그후 탐색을 진행하면서 하나씩 더해나갔습니다.
이때 map의 다음방이 이전방의 값보다 1 크다면 ans 값에 전방의 확률 * 진행방향의 확률 을 더해주었습니다
탐색은 map값이 n+1 이 나오는 순간 멈추었고
마지막에 map == n+1인 방들의 확률을 더해 출력했습니다 왜 틀릴까요... ㅋㅋㅋㅋ 슬프네요