문제 소개
n개의 정점으로 구성된 무방향 트리가 하나 주어진다고 가정해 봅시다. 정점에는 1부터 n까지 번호가 붙어 있습니다. 개구리는 정점 1에서 점프를 시작하며, 현재 정점과 인접한 아직 방문하지 않은 정점으로 1초에 한 번씩 점프할 수 있습니다. 단, 이미 방문한 정점으로는 되돌아갈 수 없습니다.
점프할 수 있는 정점이 여러 개라면 개구리는 동일한 확률로 그중 하나를 무작위로 선택해 이동하고, 더 이상 이동할 곳이 없다면 같은 정점 위에 영원히 머무르게 됩니다.
트리는 간선(edge) 배열의 형태로 주어지며, 우리가 구해야 하는 값은 t초 후 개구리가 target 정점 위에 있을 확률입니다.
예시
입력이 n = 7, t = 2, target = 4이고 트리가 아래와 같을 때 −
출력은 0.1666이 됩니다. 그래프를 보면 개구리는 정점 1에서 시작하여 1초 후 0.3333의 확률로 정점 2로 점프한 뒤, 이어서 2초 후 0.5의 확률로 정점 4로 점프합니다. 따라서 2초 후 개구리가 정점 4에 있을 확률은 0.3333 × 0.5 ≈ 0.1667(0.166667)입니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다 −
- ret := 1로 초기화합니다.
- 방문한 정점을 기록할 집합(set) visited를 정의합니다.
- dfs() 함수를 정의합니다. 이 함수는 node, start, 간선 리스트 g, time, t, 스택 st를 매개변수로 받습니다.
- node가 visited에 이미 존재하면 false를 반환합니다.
- node를 visited에 추가합니다.
- node가 1과 같다면 tt := time, ok := true로 설정한 뒤 true를 반환합니다.
- i := 0부터 g[node]의 크기 미만까지 1씩 증가시키며 반복합니다 −
- g[node][i]를 st에 push합니다.
- dfs(g[node][i], start, g, time + 1, t, st)의 결과가 true이면 true를 반환합니다.
- 그렇지 않으면 st에서 요소를 pop합니다.
- false를 반환합니다.
- 메인 메서드에서는 다음을 수행합니다 −
- ret := 1, ok := false로 초기화합니다.
- 크기가 n + 1인 리스트 배열 graph와 graph2를 정의합니다.
- i := 0부터 edges의 크기 미만까지 반복하며 graph[edges[i][0]]에 edges[i][1]을, graph[edges[i][1]]에 edges[i][0]을 추가해 양방향 그래프를 구성합니다.
- 스택 st를 정의합니다.
- dfs(target, target, graph, 0, t, st)를 호출해 target에서 정점 1까지의 경로를 역으로 찾습니다.
- 스택이 비어 있지 않은 동안 반복합니다 −
- node := st의 최상위 요소
- sz := graph[node]의 크기 (단, node가 1이 아니면 1 감소)
- ret := ret × (1.0 / sz)
- st에서 요소를 pop합니다.
- tt > t이면 0을 반환합니다. (target에 도달하는 데 필요한 시간이 t를 초과하는 경우)
- tt == t이면 ret을 반환합니다.
- tt < t && target == 1 && graph[target].size() >= 1이면 0을 반환합니다.
- 마지막으로, tt < t이면서 graph[target].size() > 1이면 0을, 그렇지 않으면 ret을 반환합니다. 개구리가 t초 이전에 도착했지만 계속 이동해야 하는 상황이라면 결국 target을 떠나게 되기 때문입니다.
다음 구현 예제를 통해 더 자세히 이해해 봅시다 −
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
double ret = 1;
bool ok;
set<int> visited;
int tt;
bool dfs(int node, int start, vector<int> g[], int time, int t,
stack<int>& st){
if (visited.count(node))
return false;
visited.insert(node);
if (node == 1) {
tt = time;
ok = true;
return true;
}
for (int i = 0; i < g[node].size(); i++) {
st.push(g[node][i]);
if (dfs(g[node][i], start, g, time + 1, t, st))
return true;
;
st.pop();
}
return false;
}
double frogPosition(int n, vector<vector<int> >& edges, int t,
int target){
ret = 1;
ok = false;
vector<int> graph[n + 1];
vector<int> graph2[n + 1];
for (int i = 0; i < edges.size(); i++) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
stack<int> st;
dfs(target, target, graph, 0, t, st);
while (!st.empty()) {
int node = st.top();
double sz = (double)graph[node].size();
if (node != 1)
sz--;
ret *= (1.0 / sz);
st.pop();
}
if (tt > t)
return 0;
if (tt == t)
return ret;
if (tt < t && target == 1 && graph[target].size() >= 1)
return 0;
return tt < t && graph[target].size() > 1 ? 0 : ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};
cout << (ob.frogPosition(7,v,2,4));
}입력
7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4출력
0.166667