[백준, Java] 16502번, 그녀를 찾아서(시뮬레이션)

문제 링크

16502번: 그녀를 찾아서

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 각 매장에서 그녀가 이동할 확률이 존재하며, 확률의 합은 1입니다.

2. 그녀는 10분마다 이동합니다.

3. n * 10분 이후에 그녀가 각 매장에 있을 확률을 결과로 출력합니다.

4. 결과의 오차는 1/100까지 허용합니다.

5. 매장은 A, B, C, D로 4개가 존재합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 시뮬레이션을 통해 그녀가 이동할 확률을 구합니다.

 

3. 구한 확률을 결과로 출력합니다.

 

 

시뮬레이션

 

첫 10분에는 각 매장에 그녀가 있을 확률은 동일하게 1이다.

 

첫 10분 그녀가 이동할 확률

매장	A	B	C	D
계산	1 × 0.6 = 0.6	1 × 1.0 = 1.0	1 × 0.3 = 0.3	1 × 1.0 + 1 × 0.7 + 1 × 0.4 = 2.1
확률	0.6 ÷ 4 = 0.15%	1.0 ÷ 4 = 0.25%	0.3 ÷ 4 = 0.075%	2.1 ÷ 4 = 0.525%

 

20분 그녀가 이동할 확률

매장	A	B	C	D
계산	0.3 × 0.6 = 0.18	0.6 × 1.0 = 0.6	1 × 0.3 = 0.3	2.1× 1.0 + 1 × 0.7 + 0.3 × 0.4 = 2.92
확률	0.18 ÷ 4 = 0.045%	0.6 ÷ 4 = 0.15%	0.3 ÷ 4 = 0.075%	2.92 ÷ 4 = 0.73%

 

 

위와 같이 계산한 내용을 확률에 맞게 반복하여 계산해주시면 됩니다.

 

예제입력 1.

위에 설명한 내용의 케이스와 동일하기 때문에 생략하겠습니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 각 매장의 이동 확률을 저장합니다.
• 그녀의 움직임을 n × 10분 동안 시뮬레이션을 진행합니다.
• 시뮬레이션이 종료된 이후 얻은 계산값으로 확률을 구합니다.
• 구한 확률의 값들을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

import java.io.*;

import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        StringTokenizer st;
        double[][] map = new double[4][4];	//매장 간 이동 확률 저장
        double[] costs = new double[4];	// 현재 각 매장에 계산 값
        double[] result = new double[4];	//확률이 저장될 값
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            char start = st.nextToken().charAt(0);
            char end = st.nextToken().charAt(0);
            double cost = Double.parseDouble(st.nextToken());
            map[start - 65][end - 65] = cost;	//각 매장 이동 확률 저장
            result[end - 65] += cost;		//첫 10분 이동할 확률 저장
            costs[end - 65] += cost;		//첫 10분 이동할 계산 저장
        }
        //n × 10분 동안 그녀가 움직이는 시뮬레이션 진행
        for(int i=1;i<T;i++){
            result = new double[4];
            for(int j=0;j<4;j++){
                if(costs[j] == 0) continue;	//계산이 0이면 확률이 있어도 0
                for(int k=0;k<4;k++){
                    if(map[j][k] == 0) continue;	//확률이 0이면 계산해도 0
                    result[k] +=  costs[j] * map[j][k];	//계산 진행!
                }
            }
            //계산한 값 확률로 이동
            for(int j=0;j<4;j++){
                costs[j] = result[j];
            }
        }
        //n × 10분의 시뮬레이션 종료 후 얻은 계산값을 통한 확률 구하기
        for(int i=0;i<4;i++) {
            bw.write(String.format("%.2f", (result[i]/4)*100));
            bw.newLine();
        }
        bw.flush();	//구한 확률 출력
        bw.close();
        br.close();

    }
}