24008번 Catch Them All
문제
번역
Codejamon GO 게임을 한다.
도시는 1부터 N까지 장소가 있으며 M개의 양방향 도로가 있고 시작 지점은 항상 1이다.
Codejamon이 랜덤 장소에 등장하면 가장 빠른 경로로 이동해 잡는다.
잡은 즉시 다른 랜덤 위치에 Codejamon이 나타난다.
총 P마리 Codejamon을 잡을 때 기대 소요 시간을 구하시오.
설계
푸키먼 고를 흉내낸 문제.
현재 장소를 제외한 무작위 위치에 푸키먼이 등장하는데
우선 각 위치에서 다른 모든 위치까지의 최단 거리를 알아야한다.
거리를 알게되면 이동시간을 구할 수 있고 이동시간을 알면 평균을 낼 수 있다.
이를 P번 반복해서 기대 소요 시간을 구한다.
구현
1. 그래프 그리기
입력받아서 그래프를 그려준다.
중복 간선이 없다는게 보장되므로 그냥 쑥쑥 집어넣기만 하면 된다.
try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
int T = Integer.parseInt(br.readLine().trim());
for (int t = 1 ; t <= T ; t++) {
StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
// 그래프 초기화
int[][] dist = new int[N + 1][N + 1];
for( int i = 1 ; i <= N ; i++) {
for (int j = 1 ; j <= N ; j++) {
// U V D가 크지않아서 적당히 큰 값 세팅
dist[i][j] = i == j ? 0 : 100000;
}
}
// 간선 등록
for (int i = 0 ; i < M ; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
int U = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
int D = Integer.parseInt(st.nextToken());
// 양방향
dist[U][V] = D;
dist[V][U] = D;
}
}
}catch(Exception e) {
e.printStackTrace();
}
2. 최단거리
플로이드 워셜 알고리즘을 사용한다.
시간 복잡도가 O(N^3) 인데 N이 크지가 않아서 괜찮을거다.
다익스트라보다 간단하다.
// 플로이드 워셜 알고리즘
// 경유지 k가 가장 바깥
for (int k = 1; k <= N ; k++) {
for (int i = 1 ; i <= N ; i++) {
for (int j = 1 ; j <= N ; j++) {
// k 를 경유해서 가는게 더 빠르면 갱신
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]) ;
}
}
}
3. 시간 계산
원래 대충 근사값 계산했는데 계속 틀렸다고해서 수학공부를 좀 진행해야했다.
단순 근사값 계산 대신 마르코프 체인을 활용해 P (최대 10^9) 에 대한 누적 기대 시간을 효율적으로 추정한다.
// 시간 계산
// 첫번째는 반드시 1번에서 출발
double start = 0.0;
for (int i = 2 ; i <= N ; i++) {
start += dist[1][i];
}
start /= (double)(N - 1);
// 같은 위치 제외 모든 거리의 평균
double result = 0.0;
for (int i = 1 ; i <= N ; i++) {
for (int j = 1 ; j <= N ; j++) {
if (i == j) continue;
result += dist[i][j];
}
}
// N * (N - 1)
result /= (N * (double)(N - 1));
// 근사값 계산했더니 틀려서 상세하게 접근
// 람다
double lambda = -1.0 / (N - 1);
// 기하급수 합
double geoSum = (1 - Math.pow(lambda, P)) / (1 - lambda);
result = result * P + (start - result) * geoSum;
bw.write(String.format("Case #%d: %.6f\n", t, result));
채점
반성
이상한 일이 있다.
분명히 처음에 예제 입력이 너무 개판이었다.
한 줄에 3개씩 숫자가 들어와야하는데 4개 2개 이렇게 개판으로 들어와서 입력을 희한하게도 주네 했는데
문제 맞추고 다시 보니 예제가 3개씩 들어오는 것으로 정상화 되어있다.
최면 걸렸나? 사이버 귀신인가?
그래서 다시 입력받는 부분 간소화하고 돌렸더니 메모리와 시간이 확 줄었다.
진짜 무슨 일이 일어난거지
코드 확인