반응형

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

 

9879번: Cross Country Skiing

The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 <= M,N <= 500), each elevation being in the range 0 .. 1,000,000,000. Some of the cells in this grid are designated as waypoints for the course. The org

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 좌표를 i * N + j를 통해 번호를 매겨줍니다.

 

2. 지도를 입력받고, 모든 노드들의 상하좌우로 인접한 노드들의 이어 차이값을 arr 배열에 저장합니다.

 

3. waypoint의 개수를 cnt에 저장합니다.

 

4. arr 배열을 D를 기준으로 오름차순으로 정렬합니다.

 

5. arr 배열을 for문을 통해 돌면서 이어주고, 부모노드가 waypoint 라면  cnt--를 해주고, D의 최댓값을 ans에 저장합니다.

 

6. cnt == 0이라면 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
struct node {
    int a;
    int b;
    int D;
};
 
bool cmp(node left, node right)
{
    return left.D < right.D;
}
 
int M, N;
int map[500][500];
vector<int> waypoint;
vector<node> arr;
int vect[250000];
int cnt = -1;
int dy[2] = { 1,0 };
int dx[2] = { 0,1 };
int ans;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &M, &N);
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
            vect[i * N + j] = i * N + j;
        }
    }
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            int num;
            scanf("%d", &num);
 
            if (num == 1) cnt++;
 
            waypoint.push_back(num);
        }
    }
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < 2; k++) {
                int ii = i + dy[k];
                int jj = j + dx[k];
 
                if (ii >= 0 && ii < M && jj >= 0 && jj < N) {
                    arr.push_back({ i * N + j, ii * N + jj, abs(map[i][j] - map[ii][jj]) });
                }
            }
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    for (auto& next : arr) {
        int pa = Find(next.a);
        int pb = Find(next.b);
        const int D = next.D;
 
        if (pa != pb) {
            if (waypoint[pa] == 1 && waypoint[pb] == 1) {
                cnt--;
            }
            else if (waypoint[pa] == 0 && waypoint[pb] == 1) {
                swap(pa, pb);
            }
 
            ans = max(ans, D);
 
            Union(pa, pb);
        }
 
        if (cnt == 0) {
            printf("%d", ans);
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13

+ Recent posts

티스토리툴바