Algorithm/Graph
[백준 (BOJ)] 1405 - 미친 로봇 (Python)
잘될거야아마두
2021. 5. 12. 21:23
1405번: 미친 로봇
첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자
www.acmicpc.net
백트랙킹 문제이다.
로봇이 이동 횟수를 모두 채울 때까지 방문하지 않은 지점만 방문한다면, 해당 경로의 확률을 정답에 더해주면 된다. 이때 방문한 지점은 (2n + 1) * (2n + 1) 크기의 행렬을 만들어서 표시했다. 한 방향으로 최대 n번 갈 수 있기 때문이다.
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
def dfs(x, y, cnt, p):
global ans
if cnt == n:
ans += p
return
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if board[nx][ny]:
continue
if not 0 <= nx < (2 * n) + 1 or not 0 <= ny < (2 * n) + 1:
continue
board[nx][ny] = 1
dfs(nx, ny, cnt + 1, p * poss[i] * 0.01)
board[nx][ny] = 0
n, east, west, south, north = map(int, input().split())
poss = [north, east, south, west] # 위의 dx, dy 랑 순서 맞춰줌
board = [[0] * (2 * n + 1) for _ in range(2 * n + 1)]
board[n][n] = 1
ans = 0
dfs(n, n, 0, 1)
print(ans)