미친 로봇 (1405번) - 백준 (BOJ)

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

1405번: 미친 로봇

 

백준 - 미친 로봇 (1405번)

 

난이도 : Gold 4

알고리즘 : DFS (Depth-First Search), Backtracking

풀이 소요 시간 : 30 mins

 

import sys
input = sys.stdin.readline


def dfs(depth, p, r, c):
    global tp
    if depth == N:
        return
    for i in range(4):
        rr, cc = r+dr[i], c+dc[i]
        if not dirs[i]:
            continue
        if visit[rr][cc]:
            tp += p * dirs[i]
            continue
        visit[rr][cc] = True
        dfs(depth+1, p*dirs[i], rr, cc)
        visit[rr][cc] = False
    return


if __name__ == '__main__':
    N, *dirs = map(int, input().split())
    dirs = list(map(lambda x: x/100, dirs))
    dr, dc = [0, 0, 1, -1], [1, -1, 0, 0]
    visit = [[False] * ((N<<1)^1) for _ in range((N<<1)^1)]
    visit[0][0] = True
    tp = 0.0
    dfs(0, 1, 0, 0)
    print(1-tp)

 

DFS (Backtracking) 로 탐색하면 해결되는 문제.

 

처음에 확률값 1.0으로 시작해서

특정 방향으로 이동할 때, 그 방향의 확률을 곱해주면 된다.

 

이미 방문한 노드를 다시 방문하는 경우 탐색을 중지하고,

1.0에서 해당 확률들을 모두 더한 값을 빼주면

그 값이 정답이 된다.