[종만북] NUMB3RS - 두니발 박사의 탈옥 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-NUMB3RS

 

 

풀이

  예제 입력의 첫 번째 테스트케이스를 그래프로 그려보면 아래와 같다.

 

  탈출 전 확률이 1(100%)이라 한다면 이후 간선을 따라, 간선이 존재하는 만큼 확률이 나뉘어져서 들어가게 된다. 탈출 전일 때 0에서 시작하므로 0은 1로 시작하고, 탈출 1일차에 0에서 갈 수 있는 간선이 1,2,3 이므로 1/3씩 나뉘어 들어간다. 그리고 2일차에 1과 3에 있던 1/3은 0으로 다시 돌아오고, 2에 있던 1/3은 0과 4로 1/6씩 나뉘어 들어가게 된다.

 

  따라서 2일차에 0에 위치는 5/6, 1,2,3 위치는 0, 4는 1/6이 된다. 이런식으로 일차별로 계속 진행한 후 q에 따라 출력해주면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine());
        while (c-->0) new Main().solution();
        System.out.print(sb);
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());

        boolean[][] edges = new boolean[n][n];
        int[] edgeCnt = new int[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                if (st.nextToken().charAt(0) == '0') continue;

                edgeCnt[i]++;
                edges[i][j] = edges[j][i] = true;
            }
        }

        double[] percentage = new double[n];
        percentage[p] = 1d;

        while (d-->0) {
            double[] tmp = new double[n];
            for (int i = 0; i < n; i++) {
                if (percentage[i] == 0) continue;

                for (int to = 0; to < n; to++) {
                    if (!edges[i][to]) continue;

                    tmp[to] += percentage[i] / edgeCnt[i];
                }
            }
            percentage = tmp;
        }

        int t = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (t-->0) {
            int q = Integer.parseInt(st.nextToken());
            sb.append(percentage[q]).append(' ');
        }
        sb.append('\n');
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.