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

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

-정답풀이:

direction=[(-1,0),(1,0),(0,-1),(0,1)]으로 방향 이동하는 리스트 구현하기 

visit.pop() 구현하기 

n번만큼 주어진 확률*100이 곱해졌을 것이므로 (0.01**n)을 ans에 곱해서 출력해주기 

def dfs(x,y,cnt,visit):
    global ans   
    if len(visit)==n+1:
        ans+=cnt
        return ans
        
    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,cnt*probability[i],visit)
            visit.pop()
            
n,E,W,S,N=(map(int,input().split()))
probability=[E,W,S,N]
direction=[(-1,0),(1,0),(0,-1),(0,1)]

ans=0
dfs(0,0,1,[(0,0)])

print(ans*((0.01)**n))

 

-처음 풀이: 

고쳐야할 점이 많은 코드이다

1. 먼저 방문한 위치를 어떻게 표현해야할지 몰랐다(문제에서 로봇은 행렬위에서 움직이는 게 아니라는 생각에 어떻게 표현해야하는지 몰랐는데, 그냥 이동하는 좌표를 하나씩 visit에 추가해주면 된다는 것을 알았다)

2. 하나의 깊이로 이동하기 때문에 중간에 ans+=cnt 코드가 있으면 cnt의 값이 계속해서 축적돼서 정확한 ans 값이 나오지 않는다 

그래서 dfs함수를 나올때 ans +=cnt를 해줘야한다 

3. probability[i] !=0 은 굳이 필요없는 코드이다 

4. 처음 숫자 input()할 때, n,e,w,s,n에서 n이 중복되므로 둘 중에 하나를 다른 문자로 변경했어야했다. 이거 발견 못해서 몇번이나 시간초과가 발생했다 

def dfs(x,y,cnt,n):
    #방문처리(위치를 어떻게 표현해야할지 몰랐다)
    global ans
    ans+=cnt
    if n==0: 
    	return ans
        
    for i in range(4):
        if probabilty[i]!=0 and not visit:
            if direction[i]=='E':
                dfs(x+1,y,cnt*probability[i],n-1)
            if direction[i]=='W':
                dfs(x-1,y,cnt*probability[i],n-1)
            if direction[i]=='S':
                dfs(x,y+1,cnt*probability[i],n-1)
            if direction[i]=='N':
                dfs(x,y-1,cnt*probability[i],n-1)
            
n,e,w,s,n=(map(int,input().split()))/100
n=n*100
probability=[e,w,s,n]
direction=['E','W','S','N']
ans=0
dfs(0,0,1,n)
print(ans)