백준[ 1405 | Python ] 미친 로봇

문제

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

풀이

로봇은 상하좌우(동서남북) 방향으로 움직인다는 조건을 고려하여 움직일 방향을 dx,dy로 미리 설정해둔다.
또한 이에 따른 확률 값을 움직일 때 마다 지정해주도록한다.

dfs탐색을 수행하며 현재의 위치를 visited배열에 넣어주고, 그에 맞는 확률 값을 갱신하여 다음 재귀를 수행한다.

이 때 마다 행동을 visited배열에 넣어주는데, 이 모든 행동의 길이가 n+1이 되면 지금 까지의 값을 갱신한다.

마지막으로 일어난 행동 만큼의 확률을 %로 표현하기 위해 0.01^n 값에 지금 까지 나온 확률을 곱해준다.

n,E,W,S,N = map(int,input().split())
probs = [E,W,S,N]
dx,dy = [-1,1,0,0],[0,0,-1,1]

def dfs(x, y, visitied, t):
    global ans
    if len(visitied) == n+1:#첫 행동은 [0,0]이다. 따라서 n+1 만큼 행동
        ans += t
        return
    for i in range(4):
        nx, ny = x + dx[i],y + dy[i]

        if [nx,ny] not in visitied:
            visitied.append([nx,ny])
            dfs(nx, ny, visitied, t*probs[i])
            visitied.pop()

ans = 0
dfs(0,0,[[0,0]],1)
print(ans * (0.01 ** n))

생각 & 정리

어떤 행동이 연속된다던지, 이 확률을 %로 표현하기 위해 0.01^n이 필요하다던지 하는 풀이로 깊지는 않다고 해도 수학적인 사고가 필요한 문제였다.
이 때문에 그렇게 어렵지 않은 DFS 문제였으나 잠깐 생각하는 시간이 필요했다.
주로 개발할 때 많이 쓰이는 수학에 대한 개념은 익혀두는 편이 좋을 것 같다.