[dfs/백준] 1405번 : 미친 로봇

- 문제 : https://www.acmicpc.net/problem/1405

 

두번째 풀이이고, 여전히 풀지 못했다ㅎ

따로 행렬을 만들어서 로봇의 움직임을 확인해야하나 싶었는데, 굳이 그렇게까지는 할 필요 없었고 로봇의 위치를 좌표로 일차 리스트인 visit에 삽입해가면서 방문 여부를 확인하면 된다 

움직임은 동,서,남,북이니까 좌표로 진행하면 된다 

한번의 움직임을 dfs로 진행하는데, 그때의 확률은 count에 누적하고, 성공할 때마다의 확률을 answer에 누적해간다 

 

dfs 풀 때마다 항상 난관에 부딪히는게 하나의 깊이의 정보를 담는 리스트를 어떻게 처리할 것인가였다 

recursion이 돌면 한번에 여러 깊이가 도는데, 그때의 정보를 어떻게 담아야하는지 몰랐다. 그래서 global도 써보고 했는데

몇 번의 풀이에서 dfs를 진행하고 사용한 리스트를 원상복귀하면 된다 

그게 다음 코드이다

 

if (nx,ny) not in visit:
            visit.append((nx,ny))
            dfs(nx,ny,count*probability[i],visit)
            visit.pop()

 

- 정답 풀이 :

import sys
input = sys.stdin.readline

n,E,W,S,N = map(int,input().split())
direction = [(0,1),(0,-1),(1,0),(-1,0)]
probability = [E,W,S,N]

def dfs(x,y,count,visit):
    global answer
    if len(visit) == n+1:
        answer += count
        return 
    for i in range(4):
        nx,ny=x+direction[i][0],y+direction[i][1]
        if (nx,ny) not in visit:
            visit.append((nx,ny))
            dfs(nx,ny,count*probability[i],visit)
            visit.pop()
            
answer=0            
dfs(0,0,1,[(0,0)])            
print(answer*(0.01**n))