알고리즘 스터디 - 1

16502

• 알고리즘 : 구현
• 난이도 : 실버3

문제

16502

접근

• 각 확률을 구하기 위해 노드를 만들어 푼다.
• dfs와 bfs 보다 구현으로 접근하는 것이 수월할 것 같다.

풀어보기

//package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
	static List<Node> list = new ArrayList<>();
	static Map<String, Double> hash = new HashMap<>();

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());
		int M = Integer.parseInt(bf.readLine());

		// M개의 상태 전이 정보 입력
		for (int i = 0; i < M; i++) {
			String[] temp = bf.readLine().split(" ");
			String start = temp[0];
			String end = temp[1];
			double weight = Double.parseDouble(temp[2]);
			list.add(new Node(start, end, weight));
		}

		// 초기 상태 확률 입력 (A, B, C, D)
		hash.put("A", 0.25);
		hash.put("B", 0.25);
		hash.put("C", 0.25);
		hash.put("D", 0.25);

		// N번의 상태 전이 반복
		for (int j = 0; j < N; j++) {
			// 다음 상태 확률을 저장할 임시 맵 생성
			Map<String, Double> nextHash = new HashMap<>();
			nextHash.put("A", 0.0);
			nextHash.put("B", 0.0);
			nextHash.put("C", 0.0);
			nextHash.put("D", 0.0);

			// 각 전이 정보를 바탕으로 다음 상태 확률 계산
			for (Node node : list) {
				String start = node.start;
				String end = node.end;
				double weight = node.weight;
				double currentProb = hash.get(start); // 현재 상태의 확률
				nextHash.put(end, nextHash.get(end) + currentProb * weight);
			}

			// 현재 상태 확률을 갱신
			hash = nextHash;
		}

		// 결과 출력 (A, B, C, D 순서대로)
		System.out.printf("%.2f\n", hash.get("A") * 100);
		System.out.printf("%.2f\n", hash.get("B") * 100);
		System.out.printf("%.2f\n", hash.get("C") * 100);
		System.out.printf("%.2f\n", hash.get("D") * 100);
	}

	static class Node {
		String start;
		String end;
		Double weight;

		Node(String start, String end, double weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}
	}
}

시행착오

• 노드를 만들고 해당 노드를 해쉬맵으로 담았지만 다음 값, 즉 한번 돌고 난 다음의 확률을 구하기 위해서는 또 다른 해쉬맵이 필요했다.