반응형

https://www.acmicpc.net/problem/1486

 

1486번: 등산

첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/24

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk

rudalsd.tistory.com

 

 

1. 지도를 입력받고, arr 배열에 높이를 저장합니다.

 

2. 각 좌표에 번호를 달고 플로이드 와샬 알고리즘을 통해 floyd[ N * M ][ N * M ] 배열에 번호별로 이동거리를 저장합니다.

 

3. floyd[ 0 ][ i ] + floyd[ i ][ 0 ]의 값이 D보다 작은 번호들 중 좌표의 높이값이 가장 큰 값을 ans에 저장합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<string>
#include<cmath>
 
using namespace std;
 
int N, M, T, D;
int arr[25][25];
int floyd[625][625];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> T >> D;
 
    for (int i = 0; i < N; i++) {
        string temp;
        cin >> temp;
 
        for (int j = 0; j < M; j++) {
            if (temp[j] >= 'a') {
                arr[i][j] = temp[j] - 'a' + 26;
            }
            else {
                arr[i][j] = temp[j] - 'A';
            }
        }
    }
 
    for (int i = 0; i < N * M; i++) {
        for (int j = 0; j < N * M; j++) {
            floyd[i][j] = -1;
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 4; k++) {
                int yy = i + dy[k];
                int xx = j + dx[k];
 
                if (yy >= 0 && yy < N && xx >= 0 && xx < M && abs(arr[yy][xx] - arr[i][j]) <= T) {
                    if (arr[i][j] < arr[yy][xx]) {
                        floyd[M * i + j][M * yy + xx] = (arr[yy][xx] - arr[i][j]) * (arr[yy][xx] - arr[i][j]);
                    }
                    else {
                        floyd[M * i + j][M * yy + xx] = 1;
                    }
                }
            }
        }
    }
 
    for (int i = 0; i < N * M; i++) {
        for (int j = 0; j < N * M; j++) {
            for (int k = 0; k < N * M; k++) {
                if (j!=k && floyd[j][i] != -1 && floyd[i][k] != -1) {
                    if (floyd[j][k] == -1 || floyd[j][k] > floyd[j][i] + floyd[i][k]) {
                        floyd[j][k] = floyd[j][i] + floyd[i][k];
                    }
                }
            }
        }
    }
 
    int ans = arr[0][0];
 
    for (int i = 1; i < N * M; i++) {
        if (floyd[0][i] != -1 && floyd[i][0] != -1 && floyd[i][0] + floyd[0][i] <= D) {
            ans = max(ans, arr[i / M][i % M]);
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31

+ Recent posts

티스토리툴바