[백준][백트래킹] 1405번 미친로봇

문제

로봇이 동서남북 4개의 방향 중에 하나를 선택해서 이동하는데 N번의 행동을 취한다. 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. 각 방향으로 이동할 확률이 주어질 때 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1405)

풀이

같은 곳을 한 번보다 많이 이동하지 않는 이동경로 = visited 배열이 0인 곳만 방문하는 경우를 의미합니다. N은 14보다 작거나 같으므로 visited 배열을 만들기 위한 값을 생각해보면 동, 서, 남, 북쪽으로만 N번 이동할 수 있으므로 (2*N)*(2*N)의 크기가 필요합니다. 출발점은 N, N이라고 생각할 수 있습니다. 그 다음은 DFS(또는 BFS)를 통해서 4개의 방향으로 이동하는 경로를 탐색합니다. 백트래킹 함수에서 파라매터로 가져야하는 변수는 지금까지의 방문횟수와 지금의 자리가 어디인지, 그리고 추가로 지금까지의 확률을 사용했습니다. 만약 방문한 곳이라면 갈 수 없고, 지금까지 방문횟수가 N+1이 되는 경우엔 N번의 행동을 취한 것이므로 그 때의 확률을 결과변수에 더해주도록 했습니다. visited 배열을 만들고, 확률 계산을 위해 double로 선언해주면 금방 해결할 수 있는 문제입니다.(사실 정답엔 0.75로만 출력이 되어 있어서 0.7500000000이라고 나오는 답을 고쳐야하나 했는데 절대/상대 오차가 10-9 까지 허용한다고 되어있으므로 문제 없이 맞았습니다를 받았습니다.)

코드

https://github.com/kswim/Algorithm/blob/master/Backtracking/1405.cpp