[백준] 1405 미친 로봇 (Javascript)

잭슨·2024년 4월 26일

DFS 백준 알고리즘 자바스크립트

알고리즘 문제 풀이

목록 보기

71/130

문제

BOJ1405_미친 로봇

풀이

요구 사항

로봇은 N번 이동하고, 임의의 확률로 상,하,좌,우로 이동한다.
이미 방문한 경로를 다시 방문하지 않는 경로를 단순한 경로라고 한다.
로봇이 단순한 경로로 이동할 확률을 구하시오

접근 방식

단순한 경로란, 로봇이 N번 이동하는 과정에서 밟은 칸이 모두 처음 방문한 칸일 경우의 경로를 말한다.
이동하는 과정을 구현하자. (시뮬레이션)
로봇은 한 번에 한 방향씩 밖에 못 움직이기 때문에 BFS보다는 DFS가 더 바람직하다.
이동하는 과정에서 이미 방문한 칸을 다시 방문하지 않도록 한다면, 단순한 경로만 구할수 있다.
N번 모두 이동했을 때 현재 칸의 확률을 변수에 누적해주고 재귀를 탈출한다.
5-1. 로봇을 이동시키며 로봇이 해당 칸으로 이동할 확률을 계산해서 칸마다 넣어주자. 시작 칸의 확률은 1(=100%)이고, 그 다음 칸부터는 $"현재 칸의 확률" \times "해당 방향으로 이동할 확률"$ 로 계산해주면 된다.

풀이

로봇의 행동을 시뮬레이션하기 위해 29*29크기의 맵을 만든다.
크기가 29*29인 이유는 N의 최대값이 14고, 상하좌우로 14칸씩 움직일 수 있도록 만들려면 29*29크기로 맵을 만들어서 로봇을 (14,14)에 위치시키면 되기 때문이다.

그리고 맵의 각 칸에 확률을 넣어주도록 하자.
시뮬레이션 시작 위치(14,14)의 확률은 1(=100%)이다. 시작위치에서는 아무것도 안해도 이미 해당 칸에 도착해있기 때문이다.
여기서 만약 왼쪽으로 이동할 확률이 50%라면 map[14][13] = 1 * 0.5 가 되는 것이다.

그리고 이동하는 과정에서 다음 칸이 이미 방문한 칸일 경우 다시 방문하지 않고 무시해준다. 이렇게 함으로써 로봇은 단순한 경로로만 이동한다.

이걸 DFS로 구현한 다음, 깊이가 N에 도달했을 때 현재 칸에 적혀있는 확률을 변수에 누적해주면 단순한 경로로 이동할 확률을 구해줄 수 있다.

코드

// 방문한 곳을 다시 방문하지 않는 경로를 단순한 경로라고 한다.
// 로봇이 단순한 경로로 이동할 확률을 구하시오.

// 29*29 크기의 배열을 만들고, 중심점에서 시뮬레이션을 시작한다.
// 네 방향을 탐색하며 이동할 위치에 "현재 칸에 적혀있는 확률" * "해당 방향으로 이동할 확률" 을 한다.
// 그러면 해당 칸으로 이동할 확률이 구해진다.
// 이미 방문한 칸일경우 방문하지 않는다.
// dfs의 최대 깊이까지 들어갔다면 그때의 확률을 acc에 누적해준다.
// 그러면 acc에는 단순한 경로로 이동할 확률만 누적된다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, east, west, south, north] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const map = Array.from({ length: 29 }, () => Array.from({ length: 29 }, () => 0));
const [x, y] = [14, 14];
map[y][x] = 1;
let acc = 0;
const percentage = [west, east, north, south].map((d) => d / 100);
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

dfs(x, y, 0);
console.log(acc === 1 ? '1.0' : acc);

function dfs(x, y, depth) {
    if (depth === N) acc += map[y][x];
    for (let i = 0; i < 4; i++) {
        // 해당 방향으로 갈 확률이 0퍼센트라면 무시
        if (percentage[i] === 0) continue;
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx <= 28 && ny <= 28 && depth < N && map[ny][nx] === 0) {
            map[ny][nx] = map[y][x] * percentage[i];
            dfs(nx, ny, depth + 1);
            map[ny][nx] -= map[y][x] * percentage[i];
        }
    }
}