[백준 / BOJ] 1405미친로봇

문제

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

1405번: 미친 로봇

로봇이 동, 서, 남, 북 4방향으로 N번 이동한다. N번 이동했을때, 방문한 지점을 한번 더 방문했다면 경로가 복잡하다고 하고, 아니라면 경로가 간단하다고 한다.

각 방향에 대한 확률과 이동하는 횟수가 주어졌을때,  로봇의 이동경로가 간단할 확률을 구하는 문제다.

 

풀이

DFS와 백트래킹으로 풀었다.

처음에는 입력받은 동, 서, 남, 북 만큼 전부 저장해주고 (25 25 25 25를 입력받으면 최대공약수로 나눠준다음 저장해서 동쪽 1개 서쪽 1개 남쪽 1개 북쪽 1개 만큼 넣어줌..) 전부 탐색해준다음에 경로가 간단할 경우 / 전체경우 를 해줄려고 했다. 하지만 최악의 경우, 4^14 * 100^14만큼 반복해서 다른방법으로 풀어야했는데,

 

이동횟수를 저장해주지않고, 간단한 경로로 가는경우의 확률을 그때그때 구해서 더해줬다.

예를들어, 4 25 25 25 25일경우, 이미 각각의 방향을 선택할 확률은 1/4이다. 항상 간단한 경로만 선택한다고 가정했을때, 간단한 경로로 가는 확률은 1/4 * 1/4 * 1/4 * 1/4 다. (한 방향을 선택할 확률이 1/4이고 4번 움직이므로)

 

이때, 이미 방문한 경로는 재방문 하지않도록 해야한다. 이렇게 하지않고 모든경우를 구해서 나눠줄경우 4^14 = 268435456가 나와서 시간초과가 난다.

방문한 경로를 재방문 하지않도록 하면 (전에 온 방향으로는 항상 갈수없으니) 4 * 3^13 = 약 6백만번 반복으로 끝난다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1405%20%EB%AF%B8%EC%B9%9C%EB%A1%9C%EB%B4%87/main.cpp