[백준] 1405. 미친 로봇 / python

출처 : www.acmicpc.net/problem/1405

1405번: 미친 로봇

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

입력

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

확률의 단위는 %이다.

출력

첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.

예제 입력 1

2 25 25 25 25

예제 출력 1

0.75

 

 

 Think Think 🔑

1. 우선은 미친 로봇이 돌아다닐 수 있는 최대 범위의 운동장을 만들어주자 만약 주어진 N=2 라면, 로봇은 현재 자기 위 치 기준으로 한 방향으로만 N번 가는 것이 최대 범위일 것이다. 이 범위가 4방향, N=2이면 아래와 같은 범위

		로봇

 

2. 처음에는 각 방향의 확률을 어떻게 처리해야 하나 고민이 많았지만 똑같이 동서남북 돌리는대로 돌리고 그냥 내가 그 확률을 따로 계산해주면 된다!

ex) 로봇이 NWE 방향 순서로 움직였고 N=0.2 W=0.3 E=0.5의 확률이 주어졌었다면 최종 확률은 0.2 * 0.3 * 0.5 = 0.03

이걸 나는 재귀로 풀거기 때문에 계속 파라미터로 설정해주면 된다.

 

3. 풀이 알고리즘은 방문하지 않은 경우에만 재귀로 한번 더 들어가는 재귀 DFS로 진행하다가 count가 문제에서 인풋으로 주어진 N번만큼 도달할 때 까지도 살아남은 ( 즉 한번도 겹치지 않고 끝까지 진행한 경우 ) 경로의 확률을 최종 출력을 위한 전역변수(total)에 더해줘간다. 마지막 재귀 호출이 끝나면 모든 경로의 탐색도 끝난것이므로 total을 프린트해주면 끝!

 

 

파이썬 코드👀