백준 4485 녹색 옷 입은 애가 젤다지?
2020. 2. 13. 10:41ㆍLearn/Algorithm
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
import java.util.Scanner;
public class jelda {
static int dx1[] = {0,1,0,-1};
static int dy1[] = {1,0,-1,0};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = 1;
int it = 0;
int jt = 0;
int cnt = 0;
while(true) {
cnt++;
N= sc.nextInt();
if(N == 0)
break;
int arr[][] = new int [N][N];
int arr2[][] = new int [N][N];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
arr[i][j] = sc.nextInt();
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
arr2[i][j] = Integer.MAX_VALUE;
arr2[0][0] = arr[0][0];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++) {
for(int k = 0; k < 4; k++)
if(i + dx1[k] >= 0 && i + dx1[k] < N && j + dy1[k] >= 0 && j + dy1[k]< N) {
it = i +dx1[k];
jt = j + dy1[k];
if(it == i-1 || jt == j-1)
if(arr2[i][j] + arr[it][jt] < arr2[it][jt]) {
DFS(it,jt,arr2,i,arr,i,j,N);
}
arr2[it][jt] = Math.min(arr2[it][jt], arr2[i][j] + arr[it][jt]);
}
}
System.out.println("Problem " + cnt + ": "+ arr2[N-1][N-1]);
}
}
public static void DFS(int n,int r, int ar2[][],int r2,int ar[][],int i , int j, int N) {
if(n == r2+2 || ar2[i][j] + ar[n][r] >= ar2[n][r])
return;
ar2[n][r] = Math.min(ar2[n][r], ar2[i][j] + ar[n][r]);
for(int iot = 0; iot < 4; iot++) {
if(n + dx1[iot] >= 0 && n + dx1[iot] < N && r + dy1[iot] >= 0 && r + dy1[iot]< N)
DFS(n + dx1[iot], r + dy1[iot], ar2, r2, ar, n , r,N);
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
|
조금 어렵게 풀었는데 DP와 DFS두개를 합쳐서 문제를 풀었다.
탐색을 DP로 쭉해주다가 역방향 탐색을 했는데 자신보다 작은 숫자가 나오면,
그 숫자에 대해서 DFS로 최신화를 통해 역방향 탐색을 완료할 수 있도록 해주었다.
'Learn > Algorithm' 카테고리의 다른 글
| 1244 SWEA 최대상금 (0) | 2020.02.18 |
|---|---|
| 3289. 서로소 집합 - SWexpert (0) | 2020.02.13 |
| 1258 SW Expert 행렬찾기 (0) | 2020.02.11 |
| 11054 가장 긴 바이토닉 부분 수열 (0) | 2020.02.11 |
| 2493 탑 (0) | 2020.02.11 |