백준 1405 미친 로봇

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

1405번: 미친 로봇

📌 해결순서

'4개의 방향중 임의로 하나를 선택한다' 를 읽고 rand 라이브러리를 빌려와서, 좌표를 이동 할때마다 이동방향을 랜덤으로 설정 해줘야하나...? 이렇게 생각했지만 갈수 있는 모든 방향에 대해서 탐색을 진행해야함을 깨닫고 백트래킹 완탐으로 풀어야 겠다고 생각했다

 

확률값을 출력해야 하므로, (단순한 경로의 수 / 로봇이 이동할수 있는 전체 경로의 수) 를 출력하면 되겠다고 생각을 한뒤 코드를 다 짜고 제출했는데 틀렸다.

이 경우에는, 로봇이 이동할수 있는 모든 방향의 확률이 같은 경우에만 맞다.

모든 예제에 대한 출력값이 맞았던 이유는,  각 방향으로 이동할 확률이 모두 같았기 떄문이다.

ex) per = [25, 25, 0, 50] 인 경우에는 동쪽으로 이동할 확률과 북쪽으로 이동할 확률이 다르다. 따라서, 전체 확률값이 다르게 나타난다.

따라서, 확률의 곱셈법칙을 이용해서 좌표를 이동하는 경우에 그 방향의 확률값을 계속 곱해주고 이동이 끝났다면 그 경로대로 이동할 확률을 계속 더해주면 된다.

 

1. 이동할수 있는 방향값이 담긴 배열, 그 방향값의 확률을 담는 배열을 만든다

2. n 이 14 이하의 자연수 이므로, (14 * 2) + 1 크기의 2차원 배열을 만들고 (14, 14) 에서 시작한다

3. 이전에 방문하지 않은 위치에 대해서만 탐색을 진행한다

4. 탐색이 끝난 좌표는 pop으로 제거해준다

 

📌 코드

import sys
input = sys.stdin.readline

input_lst = list(map(int, input().split()))
n = input_lst[0]
dir_lst = [[0, 1], [0, -1], [-1, 0], [1, 0]]
# 이동할 수 있는 방향값
move_lst = []
# 이동할 수 있는 방향에 대한 확률값
per = []

for i in range(1, len(input_lst)):
    if input_lst[i] != 0:
        move_lst.append(dir_lst[i - 1])
        per.append(input_lst[i] / 100)

visited = [(14, 14)]
ans = 0


def dfs(x, y, total):
    global ans
    if len(visited) == n + 1:
        ans += total
        return

    # 이동할 수 있는 좌표에 대해서만 탐색을 진행함
    for i in range(len(move_lst)):
        nx = x + move_lst[i][0]
        ny = y + move_lst[i][1]
        if (nx, ny) not in visited:
            visited.append((nx, ny))
            dfs(nx, ny, total * per[i])
            visited.pop()


dfs(14, 14, 1)
print(ans)