1. 문제 설명
(1) 위험한 살인마 두니발 박사가 감옥에서 탈출했다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만
쉽사리 잡히지 않았다.
(2) d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수를 찾았고, 그는 감옥에 남겨둔 노트를 분석하여
아래와 같은 가설을 세웠다.
| 1 | 두니발 박사는 검문을 피해 산길로만 이동한다. |
| 2 | 두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다. |
| 3 | 두니발 박사는 수색을 피하기 위해 매일 인접한 마을로 움직여 은신한다. |
(3) 이 3개의 가설을 검증하기 위해 교도소로부터 산길로 연결된 N개 마을들의 지도를 아래의 그림과 같이 구했다.
* ex) 지도의 3번에 교도소가 있다고 가정하면, 두니발 박사는 0번, 1번, 2번, 4번, 5번 중의 도시를 임의로
골라 도망친다. 따라서 1일 후에 두니발 박사가 0번에 숨어 있을 확률은 1/5이고 2일 후에 1번 마을에 숨어
있을 확률은 1/15(1/5*1/3)가 된다.
(4) 이때 두니발 박사는 이 가설에 맞춰 행동하고 움직일 수 있는 마을이 여러 개일 경우 그 중의 하나를 임의로
선택했다고 하였을 때 d일 후에 두니발 박사가 각 마을에 있을 확률을 찾는 프로그램을 작성하시오.
2. 입출력 조건 및 예제
입력 조건
(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)
(2) 그 후 각 줄에 지도에 포함된 마을의 수 N(2<=N<=50)과 탈출 후 지금까지 지난 일수 D(1<=D<=100) 그리고
교도소가 있는 마을 P(0<=P<=N)
(3) 그 후 N줄에는 각각 N개의 정수로 행렬 A
* i번 행의 j번 숫자 A[i][j]가 1인 경우 i번 마을에서 j번 마을을 잇는 산길이 있을을 의미하며, 0인 경우 길이 없다는
것을 의미
(4) 그 다음 줄에 확률을 계산할 마을의 수 T(0<=T<=N)
(5) 그 다움 줄에 T개의 정수로 확률을 계산할 마을의 번호 Q(0<=Q<=T)
출력 조건
(1) 각 테스트 케이스마다 T개의 실수로 각 마을에 두니발 박사가 숨어있을 확률을 출력
(2) 10^-7 이하의 절대/상대 오차가 있는 경우 정답 처리
입력 예제
: 다 입력하기 힘들 것이니 복붙해서 붙여넣기 하자.
2
5 2 0
0 1 1 1 0
1 0 0 0 1
1 0 0 0 0
1 0 0 0 0
0 1 0 0 0
3
0 2 4
8 2 3
0 1 1 1 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 0 0 0 0
1 1 1 0 1 1 0 0
0 0 0 1 0 0 1 1
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 1 1 0 0
4
3 1 2 6
출력 예제
0.8333333333333333 0.0 0.16666666666666666
0.43333333333333335 0.06666666666666667 0.06666666666666667 0.06666666666666667
3. 제약 조건
(1) 프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 한다.
4. 가정법
X
5. 기저 사례
(1) 지난 일수가 지났다면 확률 계산
(2) 지난 일수가 지났다면 확률 계산
6. 코드 및 풀이
: (1) 완전 탐색과 (2) 메모제이션 두 개의 코드가 존재한다.
(1)은 완전 탐색 방법이다. 예제 입력 첫 번째를 아래의 그림처럼 표현했다.
2일 후에 두니발 박사가 0번 마을에 있을 수 있는 시나리오는 다음과 같다.
| 1 | 첫날 1번 마을로 도망갔다 다음날 0번 마을로 돌아옴 |
| 2 | 첫날 2번 마을로 도망갔다 다음날 0번 마을로 돌아옴 |
| 3 | 첫날 3번 마을로 도망갔다 다음날 0번 마을로 돌아옴 |
이때 1과 2, 3 확률은 각각 (1/2*1/3), (1/3), (1/3) 이다. 그리고 이것을 각각 더하면 예제 출력과 같이
5/6 약 0.83333을 얻을 수 있다.
이렇게 손으로 풀어보면서 가능한 모든 시나리오를 구하여 확률을 계산해본다.
(1) 완전 탐색
public class NUMB3RS_1 {
private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
private static StringBuilder sb = new StringBuilder();
// 각각 마을의 수, 지난 일수, 교도소가 있는 마을 변수
private static int N, D, P;
// 넘겨주기 위한 인수값
private static ArrayList<Integer> arr;
// 마을 i와 j가 연결되어 있는지 확인하는 행렬 변수
private static int[][] A;
// 마을 i와 연결된 마을의 수 변수
private static int[] degree;
// 각각 계산할 마을의 수와 T개의 정수로 확률을 계산할 마을의 번호 변수들
private static int T;
private static int[] Q;
private static int[][] cache;
public static void main(String[] args) throws IOException {
StringTokenizer st;
int C = Integer.parseInt(sc.readLine());
for(int i=0; i<C; i++) {
cache = new int[101][101];
st = new StringTokenizer(sc.readLine());
N = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
// 교도소 위치를 넣어주고 인자값에게 넘겨준다.
P = Integer.parseInt(st.nextToken());
arr = new ArrayList<>();
arr.add(P);
// y와 x가 서로 연결되었는 지 확인하는 과정
// 0이면 연결되지 않았고 1이면 연결되어 있다.
A = new int[N][N];
degree = new int[N];
for(int y=0; y<N; y++) {
st = new StringTokenizer(sc.readLine());
for(int x=0; x<N; x++) {
A[y][x] = Integer.parseInt(st.nextToken());
// 만약 마을과 연결되었다면 degree[y]++
if(A[y][x]==1) {
degree[y]++;
}
}
}
T = Integer.parseInt(sc.readLine());
Q = new int[T];
st = new StringTokenizer(sc.readLine());
for(int y=0; y<T; y++) {
Q[y] = Integer.parseInt(st.nextToken());
}
for(int y=0; y<T; y++) {
sb.append(solve(arr, y)+ " ");
}
sb.append("\n");
}
System.out.println(sb);
}
private static double solve(ArrayList<Integer> path, int i) {
// 기저 사례(1): 지난 일수가 지났다면
if(path.size()==D+1) {
// 원하는 Q[i]가 아니라면 0.0리턴
if(path.get(path.size()-1)!=Q[i]) return 0.0;
// Q[i]가 일치하므로 확률 계산
double ret = 1.0;
for(int y=0; y+1<path.size(); y++) {
ret /= degree[path.get(y)];
}
return ret;
}
double ret=0;
// 경로의 다음 위치를 결정
for(int there=0; there<N; there++) {
int from = path.get(path.size()-1);
if(A[from][there]==1) {
path.add(there);
ret += solve(path, i);
path.remove(path.size()-1);
}
}
return ret;
}
}
(2)의 코드는 (1) 완전탐색을 기준으로 메모제이션을 수행하는 것인데, 이대로는 바로 사용할 수 없다.
이전에 선택한 조각들에 대한 정보를 가능한 한 최소한도로 줄일 필요가 있다.
그러므로 solve()을 재귀호출 할 때 아래의 표처럼 ArrayList의 path 변수의 용도를 가지고 이용하면 된다.
| 1 | path 변수 대신 현재 위치 here 변수와 탈옥 후 지난 날짜 days 변수를 재귀 호출에 전달 |
| 2 | 전체 경로의 확률을 계산하는 것이 아닌, 현재 위치에서 시작해서 남은 날짜 동안 움직여 Q[i]에 도달할 확률 계산 |
그러므로 아래의 그림을 통해 부분 문제를 정의 할 수 있다.
* 두니발 박사가 days일째에 here번 마을에 숨어 있을때, 마지막 날에 q번 마을에 있을 조건부 확률을 반환
이때 here와 연결된 도시들의 집합을 adj(here)라고 할 때, 아래의 그림이 성립된다.
그러므로 조건부 확률은 아래의 그림처럼 구할 수 있을 것이다.
* 어떤 경로 A는 {a(0), a(1), ... , a(d)}
(2) 메모제이션
public class NUMB3RS_2 {
private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
private static StringBuilder sb = new StringBuilder();
// 각각 마을의 수, 지난 일수, 교도소가 있는 마을 변수
private static int N, D, P;
// 넘겨주기 위한 인수값
private static ArrayList<Integer> arr;
// 마을 i와 j가 연결되어 있는지 확인하는 행렬 변수
private static int[][] A;
// 마을 i와 연결된 마을의 수 변수
private static int[] degree;
// 각각 계산할 마을의 수와 T개의 정수로 확률을 계산할 마을의 번호 변수들
private static int T;
private static int[] Q;
private static double[][] cache;
public static void main(String[] args) throws IOException {
StringTokenizer st;
int C = Integer.parseInt(sc.readLine());
for(int i=0; i<C; i++) {
cache = new double[51][101];
st = new StringTokenizer(sc.readLine());
N = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
// 교도소 위치를 넣어주고 인자값에게 넘겨준다.
P = Integer.parseInt(st.nextToken());
arr = new ArrayList<>();
arr.add(P);
// y와 x가 서로 연결되었는 지 확인하는 과정
// 0이면 연결되지 않았고 1이면 연결되어 있다.
A = new int[N][N];
degree = new int[N];
for(int y=0; y<N; y++) {
st = new StringTokenizer(sc.readLine());
for(int x=0; x<N; x++) {
A[y][x] = Integer.parseInt(st.nextToken());
// 만약 마을과 연결되었다면 degree[y]++
if(A[y][x]==1) {
degree[y]++;
}
}
}
T = Integer.parseInt(sc.readLine());
Q = new int[T];
st = new StringTokenizer(sc.readLine());
for(int y=0; y<T; y++) {
Q[y] = Integer.parseInt(st.nextToken());
}
for(int y=0; y<T; y++) {
initCache();
sb.append(solve(P, 0, y)+ " ");
}
sb.append("\n");
}
System.out.println(sb);
}
private static double solve(int here, int days, int i) {
// 기저 사례(1): 지난 일수가 지났다면
if(days==D) return (here==Q[i]?1.0:0.0);
if(cache[here][days] > -0.5) return cache[here][days];
double ret = 0.0;
for(int there=0; there<N; there++) {
if(A[here][there]==1) {
ret += solve(there, days+1, i)/degree[here];
}
}
return cache[here][days] = ret;
}
// 캐시를 -1.0으로 초기화
private static void initCache() {
for(int y=0; y<N; y++) {
for(int x=0; x<101; x++) {
cache[y][x] = -1.0;
}
}
}
}
7. 시간 복잡도
- 부분 문제 O(ND)와 부분 문제를 각각 O(N) 시간에 계산되므로, 전체 시간 복잡도는 O(N^2D)가 된다,
'알고리즘 (with JAVA) > 동적 계획법' 카테고리의 다른 글
| 폴리오미노 (난이도: 중) (2) | 2022.10.11 |
|---|---|
| 비대칭 타일링 (난이도: 하) (0) | 2022.10.07 |
| 장마가 찾아왔다 (난이도: 하) (0) | 2022.10.06 |
| 우물을 기어오르는 달팽이 (난이도: 하) (2) | 2022.10.04 |
| 삼각형 위의 최대 경로 개수 세기 (난이도: 중) (0) | 2022.10.04 |