[백준] 1405번 : 미친로봇

1405번: 미친 로봇

해당 문제는 완전탐색과 확률 문제입니다. 이동경로가 단순하다는 것은 로봇이 같은 곳을 한번보다 많이 이동하지 않을때, 즉 이미 방문한 방향을 또 방문하지 않아야 합니다. 동서남북으로 이동한다는 것은 그래프에서 상하좌우로 이동한다는것이고 로봇은 최대 N번의 행동을 취할 수 있으니, 우리는 열이 N2 행이 N2인 그래프를 생성합니다.

그래프를 생성한뒤 로봇이 방문해 가면서 또 방문하지않는 조합을 방문하면서 N번 다 방문 했을경우 전체의 확률에 적용시킵니다.

동서남북으로 이동할 확률은 각각 독립적이기때문에 이동 할 때마다 곱해주면서 확률을 계산합니다.

마지막 N번 행동을 취했을때에는 이동할 확률의 합을 구해야함으로, Total에 누적시켜줍니다.

Total을 누적한 값을 결과로 출력하면 끝!!

percent = list(map(int, input().split())) # 동 서 남 북 각 확률 만큼 방문한다.
N = percent.pop(0)
SIZE = 2*N+1
graph = [[0 for _ in range(SIZE)] for _ in range(SIZE)] # 동서남북을 움직이기 위한 2N+1 배열 생성
move = ((0, 1), (0, -1), (1, 0), (-1, 0)) # 동, 서, 남, 북

ans = 0
def dfs(j,i,p, depth):
    global ans
    if depth == N:
        ans += p
        return

    for m in range(len(move)):
        ny, nx = i + move[m][0], j + move[m][1]
        if SIZE > ny >= 0 and SIZE > nx >= 0 and graph[ny][nx] == 0: # 이미 방문하지 않은 위치만 방문한다.
            graph[ny][nx] = 1
            newp = percent[m] / 100
            dfs(ny, nx, p*newp, depth+1)
            graph[ny][nx] = 0

for i in range(4):
    graph[N][N] = 1
    dfs(N, N, percent[i] / 100, 0) # N, N 좌표로 시작하여 동,서,남,북을 모두 다 방문해본다.
    graph[N][N] = 0

print(ans)