[JavaScript] 백준 1405 미친 로봇 (JS)

문제 링크

문제 설명

로봇이 동 서 남 북 중 1개를 선택하여 N번 움직일 때 로봇이 같은 곳을 다시 안가게 되는 확률을 구하는 문제이다.
입력으로 몇번 움직일지(N), 동 서 남 북 으로 움직일 확률이 주어진다.
ex) - [N, 동, 서, 남, 북]

추가 조건

• N은 14보다 작은 자연수
• 확률을 백분율(%)로 주어진다.

풀이 과정

우리는 로봇이 같은 곳을 2번 가게 되는 확률을 구해서 전체 확률에서 빼줄 것이다.
그럼 우리는 우선 로봇의 이동에 따른 visited 배열이 필요하다.
여기서 로봇은 상하좌우로 최대 14칸을 가기 때문에 30 * 30의 배열이면 될 것이다.

또한 우리는 DFS(깊이 우선 탐색)을 이용할 것인데
여기서 우리가 필요한 것은 다음과 같다.

• 로봇의 x 좌표
• 로봇의 y 좌표
• 이동 횟수
• 현재 위치까지 올 확률

내가 구현한 DFS(x, y, cnt, percent)로직은 다음과 같다.

• 만약 현제 위치의 visited 배열이 2일 경우 percent를 저장, 함수 종료
• 만약 cnt가 N일 경우 함수 종료
• 반복문(동 서 남 북)을 통해 로봇이 움직일 위치 지정
  • 만일 해당 방향으로 움직일 확률이 0이 아니라면
    • visited배열 값 +1
    • (다음 X 좌표, 다음 Y 좌표, cnt + 1, percent * 움직일 확률)로 재귀
    • 만약 DFS를 빠져나왔을 경우를 위해 visited배열 값 -1

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync('/dev/stdin').toString().trim().split(" ").map(Number);

    let N = input.shift();
    const max = 30;
    let visited = new Array(max);
    for (let i = 0; i < visited.length; i++) {
        visited[i] = new Array(max).fill(0);
    }
    let result = 0;
    const DFS = (x, y, cnt, percent) => {
        if (visited[x][y] === 2) {
            result += percent;
            return;
        }
        if (cnt === N) {
            return;
        }
        const dx = [1, -1, 0, 0];
        const dy = [0, 0, -1, 1];

        for (let i = 0; i < dx.length; i++) {
            const nextX = dx[i] + x;
            const nextY = dy[i] + y;
            if (input[i] !== 0) {
                const nextPercent = input[i] * 0.01;
                visited[nextX][nextY]++;
                DFS(nextX, nextY, cnt + 1, percent * nextPercent);
                visited[nextX][nextY]--;
            }
        }
    };
	// 시작 위치 
    visited[14][14] = 1;
	//중간 지점인 14,14에서 시작 
    DFS(14, 14, 0, 1);
    console.log(1 - result);

### 후기

---

그 동안 BFS에서 자주 사용했던 [1,-1,0,0] 배열과 같은 것을 DFS에서 사용할 수 있던 문제였다.
처음에 어떤 값을 매개변수로 넣고 재귀를 해야할지 모르겠어서 고민하는데 시간이 오래걸린 문제였던 것 같다.