[백준 (BOJ)] 1405 - 미친 로봇 (Python)

1405번: 미친 로봇 (acmicpc.net)

1405번: 미친 로봇

 

백트랙킹 문제이다.

 

로봇이 이동 횟수를 모두 채울 때까지 방문하지 않은 지점만 방문한다면, 해당 경로의 확률을 정답에 더해주면 된다. 이때 방문한 지점은 (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)