[백준] 1405 미친 로봇, python

https://www.acmicpc.net/problem/1405

 

 

백트래킹을 사용해 모든 경로를 구한다.

4 방향에 대해 다음 좌표를 정한다. 확률이 0인 방향은 제외한다.

만약 현재 좌표가 범위밖이거나 방문했던 좌표라면 건너뛴다.

dfs를 통해 탐색한 모든 경로는 단순한 경로임이 보장된다.

import sys
input = sys.stdin.readline

arr = list(map(int, input().split()))
n = arr[0]
p = [x/100 for x in arr[1:]]

visited = [[False for _ in range(2*n+1)] for _ in range(2*n+1)]
answer = 0

def dfs(cx,cy,route,prob):
    global answer 

    if route == n:
        answer += prob
        return

    d = [[0,1],[0,-1],[1,0],[-1,0]]

    for i in range(4):
        if p[i] == 0:
            continue

        dx,dy = d[i]
        nx, ny = cx+dx, cy+dy
        if nx<0 or nx>2*n or ny<0 or ny>2*n or visited[nx][ny]:
            continue
        
        visited[nx][ny] = True
        dfs(nx,ny,route+1,prob*p[i])
        visited[nx][ny] = False

visited[n][n] = True
dfs(n,n,0,1)

print(answer)