BOJ 1405 - 미친 로봇 (Python)

G4, DFS

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

풀이

• dfs 방식으로 현재 경로를 이어나가면서 특정 경로를 만드는 경우의 수를 구하고,
  이러한 경우의 수들을 모두 더한다.
• 처음에 bfs로 접근해서 애를 먹었다.

# 미친로봇, G4
lst = list(map(int, input().split()))
n = lst[0]

probability = [0.01 * i for i in lst[1:]]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]  # E W S N

start = (0, 0)
visited = set()
visited.add(start)


def dfs(x, y, cnt, prob):
    if cnt == 0:
        return prob
    
    total_prob = 0
    
    for i in range(4):
        if probability[i] == 0:
            continue
        nx, ny = x + dx[i], y + dy[i]
        if (nx,ny) not in visited:
            visited.add((nx, ny))
            total_prob += dfs(nx, ny, cnt - 1, prob * probability[i])
            visited.remove((nx, ny))
            
    return total_prob

res = dfs(0, 0, n, 1)
print(res)