★ solved.ac 난이도 : G5
(2021년 12월 29일 기준)
[문제 링크]
1405번: 미친 로봇
첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자
www.acmicpc.net
[문제 분석]
DFS와 가지 치기를 활용한 문제 (탑코더 빨간 책에도 있는 문제!!)
[풀이]
이 문제는, 탑코더 빨간 책에도 나와있는 문제입니다.
(심지어 입력 값의 범위도 같다는 점...)
여기에서는, DFS 탐색 도중 이미 움직인 지점으로 가는 경우에 가지 치기를 사용했습니다.
(가지 치기는, 불필요한 탐색을 줄이는 방법입니다.)
DFS는 재귀 함수로 구현하였고, 탐색 함수를 종료하면서 나올 때 마크했던 부분을 초기 상태로 돌려놓았습니다.
(자세한 내용은 아래의 소스를 참고해주세요~!)
[소스 코드]
만약 틀린 부분이 있다면 지적 부탁드릴게요~! (댓글 환영!!)