[백준] 1405번 미친 로봇 풀어보기 [Java]

단순한 DFS문제였다. 퍼센트를 구하는 거여서, 약간 어떻게 구하지라는 조금의 의문은 있었지만 단순했다!!

 

👨‍🏫 풀이

인풋을 100으로 나눠주어, 퍼센트로 나타내준다!!
맵이 아니기 때문에, 나가는 것이 존재하지 않기 때문에 충분히 큰 visited를 체크하는 배열을 만들어준다.(움직일 수 있는 최대 숫자가 14이기 때문에 나는 [30][30] 배열을 만들었다)

dfs를 진행하면 된다. 만약 N만큼 움직였다면, 현재 퍼센트를 ans에 더해준다. 이전에 방문했던 적이 있다면 단순하지 않은 이동경로이기 때문에 가지 않는다!!

 

👨🏻‍💻 코드

package 번1405;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] mX = {0,0,1,-1}; // 동서남북
    static int[] mY = {1,-1,0,0};
    static double ans = 0;
    static double[] dP;
    static boolean[][] isVisited;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        dP = new double[4];
        for(int i = 0 ; i < 4 ; i++) {
            dP[i] = (double) Integer.parseInt(st.nextToken()) / 100;
        }
        isVisited = new boolean[31][31];
        isVisited[15][15] = true;
        dfs(15, 15, 0, 1);
        System.out.println(ans);
    }

    private static void dfs(int x, int y, int cnt, double percent) {
        if(cnt == N) {
            ans += percent;
        } else {
            for(int i = 0 ; i < 4 ; i++) {
                int nX = x + mX[i] ; int nY = y + mY[i];
                if(isVisited[nX][nY]) continue;
                isVisited[nX][nY] = true;
                dfs(nX , nY , cnt + 1, percent * dP[i]);
                isVisited[nX][nY] = false;
            }
        }
    }
}