[백준 01405] 미친 로봇 [Python]

문제

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

 

---

풀이

로봇이 확률에 따라 상하좌우로 움직인다고 한다.

이동 가능한 모든 경로에 대해, 방문하지 않은 곳을 방문하는 비율을 구하는 문제로 재해석할 수 있다.

주어진 상하좌우로 움직이는 확률을 방향 좌표와 함께 묶어주자.

문제에서 주어진 N은 14이기 때문에 -14 ~ 14를 고려해 보드의 크기는 29면 충분하다.

if __name__ == '__main__':
    visited = [[False] * 29 for _ in range(29)]
    
    # Input
    N, *D = map(int, input().split())
    D = [(*point, d * 0.01) for point, d in zip([(0, 1), (0, -1), (1, 0), (-1, 0)], D)]
    

초기 시작 위치는 중앙인 (14, 14)이고, 이동 횟수와 초기 확률을 0과 1로 DFS를 진행했다.

    # Solve & Output
    print(dfs(14, 14, 0, 1))

DFS로 방문하지 않은 곳을 방문하며 해당 방향에 대한 확률을 곱해주었다.

한 정점에 대한 방문이 끝날 때 마다 계산한 확률들을 모두 합하고 반환했다.

def dfs(x, y, cnt, p):
    if cnt == N:
        return p
    res = 0
    visited[x][y] = True
    for dx, dy, np in D:
        nx, ny = x + dx, y + dy
        if is_valid(nx, ny):
            visited[nx][ny] = True
            res += dfs(nx, ny, cnt + 1, p * np)
            visited[nx][ny] = False
    return res

def is_valid(x, y):
    return 0 <= x < 29 and 0 <= y < 29 and not visited[x][y]

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01405.py