[코딩테스트] 백준 - 그녀를 찾아서

그녀를 찾아서  16502번 [15일차]

시간제한	메모리 제한
2초	512MB

문제

 그녀와 백화점을 가면 우리는 각자 따로따로 매장을 돌아다닌다. 중간에 그녀를 만나려면 어느 매장으로 가봐야 할까? 그녀는 백화점 쇼핑 중에는 전화벨로 방해받고 싶지 않아서 핸드폰을 꺼놓고 있다.

우리는 주어진 시간에 각 매장별로 그녀가 그 곳에 있을만한 확률을 보여주는 프로그램을 만들려고 한다.

입력은 유한한 그래프와 양의 정수이다. 그래프는 그녀의 움직임을 모델한 것이고, 움직임은 10분 단위로 일어난다고 하자. 양의 정수는 백화점에서 헤어진지 몇 10분 째인지를 나타낸다. 그래프의 노드는 매장을 의미하고, 노드 사이의 화살표는 한 매장에서 다른 매장으로 이동하는 관계이고, 화살표에는 그 이동의 확률이 표현되어 있다. 한 노드에서 바깥으로 가는 화살표가 여럿 있을 수 있는데 그 화살표 들에 적혀있는 확률들의 합은 반드시 1이어야 한다. 그녀가 백화점으로 들어와서 처음으로 방문하는 매장은 주어진 매장들 중에 같은 확률로 (무작위로) 정해진다고 하자

예를 들어, 그래프가

이면, A매장에서 B매장으로 항상 가고, B매장에서는 30% 확률로 C매장으로 움직이고, 등등.

이 경우, 임의의 매장에서 쇼핑을 시작해서 그녀가 10분후에 각 매장에 있을 확률은 A 15%, B 25%, C. 7.5%, D 52.5% 이다. 20분후는 각각 4.5%, 15%, 7.5%, 73% 이다.

위와 같은 결과를 계산하는 프로그램을 작성하라. 매장은 네개(A, B, C, D)로 정해져 있다고 가정한다. 입력은 다섯 매장을 다니는 그녀의 움직임 그래프와 쇼핑시간 (단위: 10분) 이다.

 

입력

첫째 줄에 쇼핑 시간 (단위: 10분)이 주어진다. 쇼핑 시간은 10보다 작거나 같은 자연수이다.셋째 줄부터 M개의 줄에는 간선의 정보가 주어진다. 간선의 정보는 시작 매장, 도착 매장, 그리고 확률이다.

둘째 줄에는 간선의 개수 M이 주어진다. (1 ≤ M ≤ 10)

 

출력

각 매장 A, B, C, D에 그녀가 있을 확률을 퍼센트 단위로 출력한다. 절대/상대 오차는 10-2까지 허용한다.

 

나의코드

package day15;

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

// 그녀를 찾아서 -  16502번
public class Solution1 {

    // 인접 리스트
    static List<HashMap<Integer, Double>> adj  = new ArrayList<>();
    // 정점 번호, 확률 저장할 HashMap이 담긴 인접 리스트 생성
    static int time;

    // 각 정점의 확률을 저장할 배열
    static double[] doubles = new double[4];


    // 확률을 구할때, 해당 경우의수가 나올수 있는 확률을 모두 더한다.
    public static void main(String[] args) throws IOException {
        // 재귀 - dfs
        // 인접 리스트

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        time = Integer.parseInt(br.readLine());
        int edge = Integer.parseInt(br.readLine());

        // 각 정점에 대한 HashMap 초기화
        for (int i = 0; i < 4; i++) {
            adj.add(new HashMap<>());
        }

        // 간선의 정보 입력 받기
        for(int i = 0;i < edge;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            char startEdge = st.nextToken().charAt(0);
            char endEdge = st.nextToken().charAt(0);
            double per = Double.parseDouble(st.nextToken());

            adj.get(startEdge - 'A').put(endEdge - 'A', per);
        }

        int count = 0;

        // 매장은 A,B,C,D 네개로 정해져있음
        for (int i = 0; i < 4; i++) {
            //탐색
            dfs(i, 0.25, count);
        }


        // 절대/상대 오차는 10-2까지 허용 -> 소수점 2번째까지 출력
        for (int i = 0; i < 4; i++) {
            System.out.printf("%.2f",doubles[i]);
            System.out.println();
        }

    }

    // DFS로 탐색해서 모든 경우를 구하고, count한다
    // count한 결과가 time과 같을때 종료되는 기저조건을 작성한다
    // 마지막에 종료될때 모든 경우에수에 나온 확률을 더해서 출력한다.
    static void dfs(int now, double v, int count){
        if(time == count){
            doubles[now] += v * 100;
            return;
        }

        // Map 의 전체 내용 출력
        for(Map.Entry<Integer, Double> entry : adj.get(now).entrySet()){
            int entryKey = entry.getKey();
            double entryValue = entry.getValue();

            dfs(entryKey, v*entryValue, count+1);

        }
    }

    // 14400kb	136ms
}