백준 1405 : 미친 로봇 - javascript(dfs)

문제 출처 

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

 

정답 풀이 

dfs를 활용해서 풀었다. 

 

임의로 그래프를 생성해서 방문한 위치인지 확인해줘야 하는데 

이때 그래프 크기는, 

세로 가로 N*2+1 크기로 두면 된다. 

 

그리고 처음 위치는 [N,N]으로 둔다 

 

확률은, 

해당 방향으로 이동했을 때 확률을 계속 곱해준후, 

N만큼 이동했을 때 총 단순환 확률에다가 더해준다. 

 

정답 코드 

const [N, e,w,s,n] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(v => +v); 

let simple = 0 

const dx = [0, 0, 1, -1] //동서남북
const dy = [1,-1, 0, 0]
const prob = [e / 100, w / 100, s / 100, n / 100];

function dfs(L, cx, cy, visited, probability){
    if(L === N){
       simple += probability
       return; 
    }
    for(let d=0; d<4; d++){
        let nx = cx + dx[d]; 
        let ny = cy + dy[d]; 
        
        if(!visited[nx][ny]){
            visited[nx][ny] = true
            dfs(L+1, nx, ny, visited, probability * prob[d])
            visited[nx][ny] = false
        }
    }
}


const visited = Array.from({length: N*2+1}).map(() => new Array(N*2+1).fill(false)); 
visited[N][N] = true; 
dfs(0,N, N, visited, 1)

console.log(simple)