그녀를 찾아서
면접 대비시간 제한2초메모리 제한512 MB
A, B, C, D 네 가게를 잇는 확률 그래프와 10분 단위 시간이 주어질 때 시간이 지난 후 각 가게에 그녀가 있을 확률을 구한다.
문제
그녀와 백화점에 가면 우리는 각자 따로 매장을 돌아다닌다. 중간에 그녀를 만나려면 어느 매장으로 가야 할까? 그녀는 쇼핑 중에 전화벨에 방해받고 싶지 않아서 핸드폰을 꺼 두었다.
주어진 시간에 각 매장별로 그녀가 그곳에 있을 확률을 보여주는 프로그램을 만들려고 한다.
입력은 유한한 그래프와 양의 정수이다. 그래프는 그녀의 움직임을 모델로 한 것이고, 움직임은 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이 주어진다. (1 ≤ M ≤ 10)
셋째 줄부터 M개의 줄에는 간선의 정보가 주어진다. 간선의 정보는 시작 매장, 도착 매장, 그리고 확률이다.
출력
각 매장 A, B, C, D에 그녀가 있을 확률을 퍼센트 단위로 출력한다. 절대/상대 오차는 10-2까지 허용한다.