백준 1405번 - 미친로봇 (JAVA)

https://www.acmicpc.net/problem/1405

문제

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

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

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

입력

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

출력

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

풀이 및 코드

메인함수

1. visited 는 방문 여부를 기록하는 배열이다.

문제 조건에서 N(이동하는횟수) 가 14 보다 작거나 같다고 하였으므로

왼쪽으로만, 오른쪽으로만 14 이동할 경우를 생각하여 14*2=28 보다 큰 30으로 선언하였다.

처음 시작 위치를 [15][15] 로 설정하면 [30][30] 그래프 밖으로 벗어날 일은 없다.

 

2. Portable 은 각 이동 확률을 담고있는 배열이다. 변수 이름을 잘못 정한 것 같음ㅎㅎ..

 

3. DFS(15,15,1)     15,15 는 DFS를 시작하는 지점이다. 1 은 누적 확률이다. 재귀함수를 수행할때마다 1 * Portable[x] 를 하여 확률이 갈수록 줄어들게 될것이다.

 

 

 

DFS 함수

1.DFS 함수이다. 재귀 종료 조건은 N=0 일때로 설정하였다.

본인은 DFS 를 수행하여 한칸 이동할 때 마다 N을 감소 시켰다. 즉 N=0 이 된 경우는 N번만큼 움직였다는 뜻이다.

 

2.DFS 를 실행하였으므로 현재 점을 방문으로 표시한다.

 

3.상단 dx, dy 를 정의 한대로 보면 for 문안의 이동방향은 다음과 같다

동쪽 : x+ d[0], y+d[0]     -    x, y+1

서쪽 : x+ d[1], y+d[1]       -    x, y-1

남쪽 : x+ d[2], y+d[2]      -    x+1,y

북쪽 : x+ d[3], y+d[3]      -    x-1,y 

 

4.if문은 다음에 방문할 nx, ny가 이미 방문한 지점인지 판단하는 것이다.

방문한 지점이라면 단순한 경로가 아니므로 더이상 DFS를 진행할 필요가 없다.(백트래킹)

방문하지 않은 지점이라면 N을 감소시키고(이동을 한다는 의미) nx, ny 에서 다시 DFS를 실행한다.

 

5.DFS에서 리턴된 후 visted[nx][ny] = true 를 다시 방문하지 않은 지점으로 해줘야 하므로 false 로 하며

이동또한 마찬가지로 N을 증가시킨다.