[DFS/재귀] 백준 1405 파이썬 (미친 로봇) 골드5

-풀이

#동서남북 4방향 탐색
direction = [(-1,0), (1,0), (0,-1), (0,1)]

def dfs(r, c, visited, total):
  global answer
  if len(visited) == N+1:
    answer += total
    return
  for idx in range(4):
    #nr:x축, nc:y축
    nr = r + direction[idx][0]
    nc = c + direction[idx][1]
    if (nr,nc) not in visited:
      visited.append((nr,nc))
      dfs(nr, nc, visited, total*percent[idx])
      visited.pop()
#동서남북
N, east, west, south, north = map(int,input().split())
percent = [east, west, south, north]
answer = 0

dfs(0, 0, [(0,0)] ,1)
print(answer * (0.01 ** N))

-풀이설명

단순한 방향으로 가는 확률은 지나간 방향을 다시 안지나갔을 경우만 경로를 탐색하면서 확률을 계산하고 단순한 방향으로 간 경로마다 그확률들을 곱하는 것이 아닌 더해주어야 한다.

내가 이 문제를 풀기위해 생각했던 범위는 단순한 방향으로 가는 경로까지는 탐색할 수 있었는데, 방향마다 확률이 다를 경우 어떤식으로 계산을 해주어야하는지 몰라서 풀이를 참고하여 풀게되었다. 

확률을 계산하는 방법은 단순한 경로 중에 이동할 방향마다의 확률을 계속 곱해주고 answer에 경로마다 확률을 더해주면 해결가능했다.