level - hard
[문제 내용]
t초동안 개구리가 움직인 위치가 target일 확률을 구하라.
1. tree에서 갔던곳은 다시 갈 수 없음
2. tree에서 더이상 갈 곳이 없을 경우 제자리에 머뭄
3. 갈 곳이 존재할 경우 무조건 전진 (갈수 있는 곳이 여러곳일 경우 random)
4. 무조건 1부터 시작
[example 1]
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666
Explanation: The figure above shows the given graph.
The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1
and then jumping with 1/2 probability to vertex 4 after second 2.
Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666. [example 2]
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 0.3333333333333333
Explanation: The figure above shows the given graph.
The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1. [example 3]
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
Output: 0.16666666666666666[해결 방법]
일단 tree가 undirect구조로 들어오지만 1부터 시작하므로 갈 수 있는 방향은 정해져있다.
1과 연결되어 있는 edge로만 움직일 수 있고 그 edge와 연결된 edge로만 움직일 수 있다.
움직일 수 있는 곳을 찾기 위해 재귀를 이용하였고,
1에서 움직일 수 있는 edge들을 저장하고
1과 연결되 edge에서 또 움직일 수 있는 edge들을 저장하여 가지고 있는다.
위의 저장된 값을 이용해 target까지 몇초안에 움직일 수 있는지 찾고
해당하는 t안에 움직일 수 있는 지 확인한후
해당 edges들을 수로 확률을 계산한다.
class Solution {
// 더 전진할 수 있는 edge들은 hashmap의 key로 저장한다.
public void generateTrees(int[][] edges, int start, HashMap<Integer, HashSet<Integer>> trees) {
for(int[] edge : edges) {
if(edge[0] == start) {
if(trees.containsKey(start) && !trees.containsKey(edge[1])) {
HashSet<Integer> tree = trees.get(start);
tree.add(edge[1]);
generateTrees(edges, edge[1], trees);
} else if(!trees.containsKey(edge[1])) {
HashSet<Integer> tree = new HashSet<>();
tree.add(edge[1]);
trees.put(start, tree);
generateTrees(edges, edge[1], trees);
}
} else if(edge[1] == start) {
if(trees.containsKey(start) && !trees.containsKey(edge[0])) {
HashSet<Integer> tree = trees.get(start);
tree.add(edge[0]);
generateTrees(edges, edge[0], trees);
} else if(!trees.containsKey(edge[0])) {
HashSet<Integer> tree = new HashSet<>();
tree.add(edge[0]);
trees.put(start, tree);
generateTrees(edges, edge[0], trees);
}
}
}
}
public double frogPosition(int n, int[][] edges, int t, int target) {
HashMap<Integer, HashSet<Integer>> trees = new HashMap<>();
// 처음시작은 무조건 1부터
generateTrees(edges, 1, trees);
ArrayList<Integer> counts = new ArrayList<>();
int buf = target;
// target이 1인 경우는 몇초안에 도달했는지 확인했다는 것
while(target != 1) {
for(int key : trees.keySet()) {
HashSet<Integer> nums = trees.get(key);
if(nums.contains(target)) {
target = key; // 1로 이동하기위해 key로 target을 변경
counts.add(nums.size()); // 확률을 계산하기 위해 해당하는 위치의 edge 개수를 저장
break;
}
}
}
double result = 0;
if(counts.size() <= t) {
// t초 보다 적게 걸려 도착하지만 더 앞으로 갈 수 있는 경우
if(counts.size() < t && trees.containsKey(buf)) {
return 0;
}
// target 이 1이거나 0초가 아닐때
if (counts.size() != 0 || buf == 1) {
result = 1;
}
// 확률 계산
for (int count : counts) {
result /= count;
}
}
return result;
}
}